#include <iostream>
//輸入一個矩陣數組,求出從arr[0][0]到arr[row - 1][col - 1]的最短路徑
int minPathSum(int (*arr)[10], const int &row, const int &col); //數組并不完全是指針,傳參數需要注意
int main()
{
int arr[10][10], num, row = 0, col = 0;
std::cin >> row >> col;
for (int i = 0; i < row; ++i)
{
for (int j = 0; j < col; ++j)
{
std::cin >> num;
arr[i][j] = num;
}
}
std::cout << minPathSum(arr, row, col);
system("pause");
return 0;
}
int minPathSum(int (*arr)[10], const int &row, const int &col)
{
if (arr == nullptr || row < 1 || col < 1)
return 0;
int **pArr = new int*[row];
for (int i = 0; i < row; ++i)
{
pArr[i] = new int[col];
}
//int pArr[10][10];
pArr[0][0] = arr[0][0];
for (int i = 1; i < row; ++i)
{
pArr[i][0] = arr[i][0] + pArr[i - 1][0];
}
for (int j = 1; j < col; ++j)
{
pArr[0][j] = arr[0][j] + pArr[0][j - 1];
}
for (int i = 1; i < row; ++i)
{
for (int j = 1; j < col; ++j)
{
pArr[i][j] = pArr[i - 1][j] < pArr[i][j - 1] ? pArr[i - 1][j] + arr[i][j] : pArr[i][j - 1] + arr[i][j];
}
}
return pArr[row - 1][col - 1];
}