简单路径的题目，其实就是在状态后面多记了有多少个独立插头。
分类讨论独立插头：
1、只存在上插头或者左插头，可以选择作为独立插头。
2、都不存在上插头和左插头，选择作为独立插头的同时要标号为新的连通块。
换行时需特别注意，因为还有独立插头的判断，如果进行了换行操作，就会乱，特别是在不存在上插头和左插头的情况下。
那要怎么办呢？
我们会发现，换行后，1~m-1往后移，并把code[0]设为0，但我们在encode的时候，code[0] = 0，其实是可以忽略的操作，那么我们只需要做M-1就可以了。
这样想来，就可以去掉shift的操作了。
1 #include <cstdio> 2 #include <cstdlib> 3 #include <cstring> 4 #include <string> 5 #include <algorithm> 6 7 using namespace std; 8 9 #define REP(i, a, b) for (int i = (a), i##_end_ = (b); i <= i##_end_; ++i) 10 #define DWN(i, a, b) for (int i = (a), i##_end_ = (b); i >= i##_end_; --i) 11 #define mset(a, b) memset(a, b, sizeof(a)) 12 const int MAXD = 15, HASH = 30007, STATE = 1000010; 13 int n, m, maze[MAXD][MAXD], code[MAXD], ch[MAXD]; 14 int text[MAXD]; 15 16 void Ckmax(int &AI, int BI) { if (AI < BI) AI = BI; } 17 18 struct HASHMAP 19 { 20 int head[HASH], nxt[STATE], state[STATE], f[STATE], siz; 21 void clear() { siz = 0, mset(head, -1); } 22 void push(int x, int add) 23 { 24 int pos = x%HASH, i = head[pos]; 25 for (; i != -1; i = nxt[i]) 26 if (state[i] == x) { Ckmax(f[i], add); return ; } 27 state[siz] = x, f[siz] = add; 28 nxt[siz] = head[pos], head[pos] = siz++; 29 } 30 }hm[2]; 31 32 void in() 33 { 34 scanf("%d %d", &n, &m), mset(maze, 0); 35 REP(i, 1, n) 36 REP(j, 1, m) scanf("%d", &maze[i][j]); 37 } 38 39 void decode(int x) 40 { 41 DWN(i, m+1, 0) code[i] = x&7, x >>= 3; 42 } 43 44 int encode(int j)//WRONG 由于换行不能修改，要这样做 45 { 46 int ret = 0, cnt = 0, lim = (j == m) ? m-1 : m; 47 mset(ch, -1), ch[0] = 0; 48 REP(i, 0, lim) 49 { 50 if (ch[code[i]] == -1) ch[code[i]] = ++cnt; 51 ret <<= 3, ret |= ch[code[i]]; 52 } 53 ret <<= 3, ret |= code[m+1]; 54 return ret; 55 } 56 57 void dp_blank(int i, int j, int cur) 58 { 59 REP(k, 0, hm[cur].siz-1) 60 { 61 decode(hm[cur].state[k]); 62 int lef = code[j-1], up = code[j]; 63 if (lef && up) 64 { 65 if (lef == up) continue ; 66 REP(t, 0, m) 67 if (code[t] == up) code[t] = lef; 68 code[j-1] = code[j] = 0; 69 hm[cur^1].push(encode(j), hm[cur].f[k]+maze[i][j]); 70 } 71 else 72 { 73 if (lef || up) 74 { 75 int t = lef ? lef : up; 76 if (maze[i][j+1]) 77 { 78 code[j-1] = 0, code[j] = t; 79 hm[cur^1].push(encode(j), hm[cur].f[k]+maze[i][j]); 80 } 81 if (maze[i+1][j]) 82 { 83 code[j-1] = t, code[j] = 0; 84 hm[cur^1].push(encode(j), hm[cur].f[k]+maze[i][j]); 85 } 86 if (code[m+1]++ < 2) 87 { 88 code[j-1] = code[j] = 0; 89 hm[cur^1].push(encode(j), hm[cur].f[k]+maze[i][j]); 90 } 91 } 92 else 93 { 94 hm[cur^1].push(encode(j), hm[cur].f[k]); 95 if (maze[i][j+1] && maze[i+1][j])//WRONG 96 { 97 code[j-1] = code[j] = 13; 98 hm[cur^1].push(encode(j), hm[cur].f[k]+maze[i][j]); 99 } 100 if (code[m+1]++ > 1) continue ; 101 if (maze[i][j+1]) 102 { 103 code[j-1] = 0, code[j] = 13; 104 hm[cur^1].push(encode(j), hm[cur].f[k]+maze[i][j]); 105 } 106 if (maze[i+1][j]) 107 { 108 code[j-1] = 13, code[j] = 0; 109 hm[cur^1].push(encode(j), hm[cur].f[k]+maze[i][j]); 110 } 111 } 112 } 113 } 114 } 115 116 void dp_block(int i, int j, int cur) 117 { 118 REP(k, 0, hm[cur].siz-1) 119 { 120 decode(hm[cur].state[k]); 121 code[j-1] = code[j] = 0; 122 hm[cur^1].push(encode(j), hm[cur].f[k]); 123 } 124 } 125 126 void work() 127 { 128 int cur = 0, ans = 0; 129 hm[0].clear(), hm[1].clear(), hm[0].push(0, 0); 130 REP(i, 1, n) 131 REP(j, 1, m) 132 { 133 if (maze[i][j]) dp_blank(i, j, cur); 134 else dp_block(i, j, cur); 135 hm[cur].clear(), cur ^= 1; 136 Ckmax(ans, maze[i][j]); 137 } 138 REP(i, 0, hm[cur].siz-1) Ckmax(ans, hm[cur].f[i]); 139 printf("%d ", ans); 140 } 141 142 int main() 143 { 144 int T; 145 scanf("%d", &T); 146 while (T --) in(), work(); 147 return 0; 148 }