题意：
有一个n * m的数字矩阵，每个格子放着一个非负整数，从左上角走到右下角，每个格子最多走一次，问所经过的格子的最大权值之和是多少，并且输出一个路径。
分析：
如果n和m有一个是偶数的话，那么只要按照蛇形的走法一直走下去即可。
比如n为奇数的时候就这样，左右左右地蛇形走。
同样的，如果m为奇数的时候，也可以上下上下地蛇形走。
但如果n和m都为偶数的时候，就会无法走完全部的格子，最终到达右下角。
但是可以少走一个格子，而且这个格子必须是那种行标加列标为奇数的格子才行(行和列从1开始)，所以我们就绕过权值最小的符合条件的格子，走其他所有的格子获得最大值。
比如像这种：
除了那个选出来的格子不走，其余的格子可以全部走到。
所以就直接这样构造出一条路径出来。
我们可以这样构造，假设选出来的不走的格子为(x, y)，把这个地图分成三部分：选第x行和相邻的一行，这两个作为一个「长城」的走法。
然后「长城」上面和下面用蛇字形走法，最后走到右下角。
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 7 const int maxn = 500 + 10; 8 9 int n, m, sum, _min; 10 int a[maxn][maxn]; 11 12 int r, c; 13 14 bool vis[maxn][maxn]; 15 16 void snake(int n, int m, char d, char revd, char nxt) 17 { 18 for(int i = 1; i <= n; i++) 19 { 20 if(i & 1) 21 { 22 for(int j = 1; j < m; j++) printf("%c", d); 23 if(i < n) printf("%c", nxt); 24 } 25 else 26 { 27 for(int j = 1; j < m; j++) printf("%c", revd); 28 if(i < n) printf("%c", nxt); 29 } 30 } 31 } 32 33 int main() 34 { 35 while(scanf("%d%d", &n, &m) == 2 && n) 36 { 37 sum = 0; 38 _min = 100000000; 39 for(int i = 1; i <= n; i++) 40 for(int j = 1; j <= m; j++) 41 { 42 scanf("%d", &a[i][j]); 43 sum += a[i][j]; 44 if(((i + j) & 1) && a[i][j] < _min) { _min = a[i][j]; r = i; c = j; } 45 } 46 47 if(n & 1) 48 { 49 printf("%d\n", sum); 50 snake(n, m, 'R', 'L', 'D'); 51 puts(""); 52 continue; 53 } 54 55 if(m & 1) 56 { 57 printf("%d\n", sum); 58 snake(m, n, 'D', 'U', 'R'); 59 puts(""); 60 continue; 61 } 62 63 printf("%d\n", sum - _min); 64 65 if(r - 2 > 0) snake(r - 2, m, 'R', 'L', 'D'); 66 if(r - 1 > 1) printf("D"); 67 68 int x, y, up, down; 69 if(r <= 2) 70 { 71 x = y = 1; 72 up = 1, down = 2; 73 } 74 else 75 { 76 up = r - 1, down = r; 77 x = r - 1; 78 if(r & 1) y = m; else y = 1; 79 } 80 81 memset(vis, false, sizeof(vis)); 82 for(int i = 0; i <= n + 1; i++) vis[i][0] = vis[i][m + 1] = true; 83 for(int i = 0; i <= m + 1; i++) vis[0][i] = vis[n + 1][i] = true; 84 vis[x][y] = true; 85 vis[r][c] = true; 86 if(y == 1) 87 { 88 for(int i = 1; i <= m * 2 - 2; i++) 89 { 90 if(x == down) 91 { 92 if(!vis[x-1][y]) { x--; vis[x][y] = true; printf("U"); } 93 else { y++; vis[x][y] = true; printf("R"); } 94 } 95 else 96 { 97 if(!vis[x+1][y]) { x++; vis[x][y] = true; printf("D"); } 98 else { y++; vis[x][y] = true; printf("R"); } 99 }100 }101 }102 else103 {104 for(int i = 1; i <= m * 2 - 2; i++)105 {106 if(x == down)107 {108 if(!vis[x-1][y]) { x--; vis[x][y] = true; printf("U"); }109 else { y--; vis[x][y] = true; printf("L"); }110 }111 else112 {113 if(!vis[x+1][y]) { x++; vis[x][y] = true; printf("D"); }114 else { y--; vis[x][y] = true; printf("L"); }115 }116 }117 }118 119 if(down + 1 <= n)120 {121 printf("D");122 if(y == 1) snake(n - down, m, 'R', 'L', 'D');123 else snake(n - down, m, 'L', 'R', 'D');124 }125 126 puts("");127 }128 129 return 0;130 }