题意：
有一个n * m的数字矩阵，每个格子放着一个非负整数，从左上角走到右下角，每个格子最多走一次，问所经过的格子的最大权值之和是多少，并且输出一个路径。
分析：
如果n和m有一个是偶数的话，那么只要按照蛇形的走法一直走下去即可。
比如n为奇数的时候就这样，左右左右地蛇形走。
同样的，如果m为奇数的时候，也可以上下上下地蛇形走。
但如果n和m都为偶数的时候，就会无法走完全部的格子，最终到达右下角。
但是可以少走一个格子，而且这个格子必须是那种行标加列标为奇数的格子才行(行和列从1开始)，所以我们就绕过权值最小的符合条件的格子，走其他所有的格子获得最大值。
比如像这种：
除了那个选出来的格子不走，其余的格子可以全部走到。
所以就直接这样构造出一条路径出来。
我们可以这样构造，假设选出来的不走的格子为(x, y)，把这个地图分成三部分：选第x行和相邻的一行，这两个作为一个「长城」的走法。
然后「长城」上面和下面用蛇字形走法，最后走到右下角。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 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 ", sum); 50 snake(n, m, 'R', 'L', 'D'); 51 puts(""); 52 continue; 53 } 54 55 if(m & 1) 56 { 57 printf("%d ", sum); 58 snake(m, n, 'D', 'U', 'R'); 59 puts(""); 60 continue; 61 } 62 63 printf("%d ", 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 else 103 { 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 else 112 { 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 }