题意：
给出一个矩阵，元素为一个数值，要求从左边做到右边，每次只走一列，输出走完时能得到的最小数值和，并且输出所走过的行数。多条路线时，输出字典序最小的。
矩阵的第一行与最后一行邻接。数值和不超过30bit的整数。
每一个位置能走的路线如图：
输入样例：
5 6
3 4 1 2 8 6
6 1 8 2 7 4
5 9 3 9 9 5
8 4 1 3 2 6
3 7 2 8 6 4
5 6
3 4 1 2 8 6
6 1 8 2 7 4
5 9 3 9 9 5
8 4 1 3 2 6
3 7 2 1 2 3
输出样例：
1 2 3 4 4 5
16
1 2 1 5 4 5
11
样例说明：
样例1
样例2
思路
当走到最后一列时，最小和为自身。
则上一列的最小和为：自身值 + min(下一列的最小值)。
计算完后访问第一列可以得到最小数值和。
利用计算时打好的dp表，先找到第一列最小的值，然后在下一列满足条件的下一个最小值，逐步记录行数，然后输出即可。
代码
#include <cstdio>
#include <cstring>
#include <algorithm>
#define INF 999999999
using namespace std;
int n, m;
int dp[11][110];
int mat[11][110];
int path[110];
int cv(int i, int a){
//得到上中下对应的行数if(i == 1 && a == -1) return n;if(i == n && a == 1) return 1;if(a == 0) return i;return i + a;
}
int dfs(int i, int j){
if(j == m) return dp[i][j] = mat[i][j];if(dp[i][j] != -1) return dp[i][j];int ans = INF;for(int a = -1; a <= 1; a++)ans = min(ans, mat[i][j] + dfs(cv(i, a), j + 1));return dp[i][j] = ans;
}
int main(){
// freopen("i.txt", "r", stdin);// freopen("o.txt", "w", stdout);while(scanf("%d%d", &n, &m) == 2){
for(int i = 1; i <= n; i++)for(int j = 1; j <= m; j++)scanf("%d", &mat[i][j]);memset(dp, -1, sizeof(dp));int ans = INF, r;for(int i = 1; i <= n; i++)if(ans > dfs(i, 1)){
r = i;ans = dfs(i, 1);}path[1] = r;for(int i = 2; i <= m; i++){
int row[3], c2 = 0;for(int a = -1; a <= 1; a++) row[c2++] = cv(r, a);//记录三个行数sort(row, row + 3);//确保每列记录的行数为字典序最小for(int j = 0; j < 3; j++)if(dp[r][i - 1] - mat[r][i - 1] == dp[row[j]][i]){
path[i] = r = row[j];//更新并记录答案行数break;}}for(int i = 1; i <= m; i++)printf("%d%c", path[i], i == m ? '\n' : ' ');printf("%d\n", ans);}
}