一.问题描述
【问题描述】假设一个矩阵mat的大小为M行N列，矩阵每个位置上有大于或等于0的整数，现从左上角[1, 1]开始，每次只能向下或向右走一步，最后到达右下角[M, N]，路径上的数字累加就是路径和。现要求最短路径和以及最短的路径。
【输入形式】在屏幕上输入矩阵大小，以及矩阵每个元素的值。
【输出形式】最短路径和，以及最短路径。
【样例1输入】
4 4
1 3 5 9
8 1 3 4
5 0 6 1
8 8 4 0
【样例1输出】
12
1 1
1 2
2 2
3 2
3 3
3 4
4 4
二.算法思路
三.代码

#include<bits/stdc++.h>
using namespace std;
int dp[20][20];
int rec[20][20];//记录数组 
void SHORTESTPATH(int m,int n){
	for(int i=2;i<=m;i++){//第一列只能由它上面的路径走来 
		dp[i][1]+=dp[i-1][1];
		rec[i][1]=1;//从上往下走 
	} 
	for(int i=2;i<=n;i++){//第一行只能由它左面的路径走来 
		dp[1][i]+=dp[1][i-1];
		rec[1][i]=2;//从左往右走 
	} 
	for(int i=2;i<=m;i++){
		for(int j=2;j<=n;j++){
			if(dp[i-1][j]+dp[i][j]<=dp[i][j-1]+dp[i][j]){
				dp[i][j]+=dp[i-1][j];
				rec[i][j]=1;
			}
			else{
				dp[i][j]+=dp[i][j-1];
				rec[i][j]=2;
			}
		}
	}
}
void TRACEBACK(int i,int j){
	if(i==1&&j==1){
		cout<<1<<" "<<1<<endl;
		return;
	}
	if(rec[i][j]==1){
		TRACEBACK(i-1,j);
	}
	if(rec[i][j]==2){
		TRACEBACK(i,j-1);
	}
	cout<<i<<" "<<j<<endl;
} 
int main(){
	int m,n;
	cin>>m>>n;
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){
			cin>>dp[i][j];
		}
	}
	SHORTESTPATH(m,n);
	cout<<dp[m][n]<<endl;
	TRACEBACK(m,n);
} 
/*
4 4
1 3 5 9
8 1 3 4
5 0 6 1
8 8 4 0
*/