看上去非常复杂， 实际上是这一系列最简单的一步，本质上是个搜索过程，相比于前一道题，可以不用策略三，而且题目的数据规模超级小，所以暴力搜索就能过。
把尚未确定的点放在一个unsettled列表里，然后依次枚举每个点的情况：是地雷or不是地雷
优化方案一即：每次枚举后，使用规则一、规则二对列表里剩下的点进行判断，如果能直接判断出是不是地雷的就立即设置了，这样剩下的枚举位就少了。当然回溯的时候记得把这些拓展出来的也要一并回溯。
优化方案二即：周围已知地雷数少的点优先枚举。（这个优化没做）
啰啰嗦嗦写了一大堆代码，WA了一次，原来是判断规则一规则二的时候单纯用8去做判断了，而一个点周围邻居点个数可能不是8。
代码：
1 #include <iostream> 2 #include <vector> 3 #include <cstring> 4 #include <cstdlib> 5 6 using namespace std; 7 8 struct point { 9 int r; 10 int c; 11 int v; 12 point(int _r, int _c) : r(_r), c(_c) {}; 13 point(int _r, int _c, int _v) : r(_r), c(_c), v(_v) {}; 14 bool operator==(const point &o) {return o.r == r && o.c == c;} 15 bool operator!=(const point &o) {return o.r != r || o.c != c;} 16 }; 17 18 #define SIZE 40 19 20 int N, M; 21 int field[SIZE][SIZE]; 22 int ans[SIZE][SIZE]; 23 int unset[SIZE][SIZE]; 24 vector<point> unsettled; 25 26 bool valid(point &p) { 27 return p.r >= 0 && p.r < N && p.c >= 0 && p.c < M; 28 } 29 30 vector<point> neighbors(point p) { 31 vector<point> res; 32 33 for (int i = -1; i < 2; i++) { 34 for (int j = -1; j < 2; j++) { 35 point q(i + p.r, j + p.c); 36 if (valid(q) && q != p) 37 res.push_back(q); 38 } 39 } 40 41 return res; 42 } 43 44 void merge(point p) { 45 if (ans[p.r][p.c] == -1 || ans[p.r][p.c] == p.v) 46 ans[p.r][p.c] = p.v; 47 else 48 ans[p.r][p.c] = -2; 49 } 50 51 int around(point p, int s) { 52 vector<point> nbs = neighbors(p); 53 int res = 0; 54 55 for (auto q : nbs) { 56 if (field[q.r][q.c] >= 0 && s == 0) { 57 res++; 58 continue; 59 } 60 else 61 res += unset[q.r][q.c] == s ? 1 : 0; 62 } 63 64 return res; 65 } 66 67 bool check(point p) { 68 vector<point> nbs = neighbors(p); 69 int mine = around(p, 1); 70 int not_mine = around(p, 0); 71 return (mine <= field[p.r][p.c] && field[p.r][p.c] + not_mine <= nbs.size()); 72 } 73 74 bool check() { 75 bool is_ok = true; 76 77 for (auto p : unsettled) { 78 if (!is_ok) 79 break; 80 vector<point> nbs = neighbors(p); 81 for (auto q : nbs) { 82 if (field[q.r][q.c] >= 0 && !check(q)) { 83 is_ok = false; 84 break; 85 } 86 } 87 } 88 89 return is_ok; 90 } 91 92 void extend() { 93 bool over = false; 94 95 while (!over) { 96 over = true; 97 for (auto p : unsettled) { 98 vector<point> nbs = neighbors(p); 99 for (auto q : nbs) { 100 if (field[q.r][q.c] < 0) 101 continue; 102 103 vector<point> os = neighbors(q); 104 int mine = around(p, 1); 105 int not_mine = around(q, 1); 106 107 if (field[q.r][q.c] + not_mine == os.size()) { 108 for (auto o : os) { 109 if (o.v == -1) { 110 over = false; 111 o.v = 1; 112 unset[o.r][o.c] = 1; 113 } 114 } 115 } 116 if (mine == field[q.r][q.c]) { 117 for (auto o : os) { 118 if (o.v == -1) { 119 over = false; 120 o.v = 0; 121 unset[o.r][o.c] = 0; 122 } 123 } 124 } 125 } 126 } 127 } 128 } 129 130 void solve(int pos) { 131 if (pos >= unsettled.size()) { 132 for (auto p : unsettled) { 133 merge(p); 134 } 135 return; 136 } 137 138 if (unsettled[pos].v != -1) { 139 solve(pos + 1); 140 unsettled[pos].v = -1; 141 unset[unsettled[pos].r][unsettled[pos].c] = -1; 142 return; 143 } 144 145 for (int i = 0; i < 2; i++) { 146 unsettled[pos].v = i; 147 unset[unsettled[pos].r][unsettled[pos].c] = i; 148 if (!check()) 149 continue; 150 extend(); 151 solve(pos + 1); 152 } 153 unsettled[pos].v = -1; 154 unset[unsettled[pos].r][unsettled[pos].c] = -1; 155 } 156 157 int main() { 158 int n; 159 160 cin >> n; 161 while (n--) { 162 cin >> N >> M; 163 memset(ans, -1, SIZE * SIZE * sizeof(int)); 164 memset(unset, -1, SIZE * SIZE * sizeof(int)); 165 unsettled.clear(); 166 for (int i = 0; i < N; i++) { 167 for (int j = 0; j < M; j++) { 168 cin >> field[i][j]; 169 if (field[i][j] < 0) 170 unsettled.push_back(point(i, j, -1)); 171 } 172 } 173 174 solve(0); 175 176 int mine = 0; 177 int not_mine = 0; 178 179 for (auto p : unsettled) { 180 mine += (ans[p.r][p.c] == 1 ? 1 : 0); 181 not_mine += (ans[p.r][p.c] == 0 ? 1 : 0); 182 } 183 184 cout << mine << " " << not_mine << endl; 185 186 } 187 188 return 0; 189 }