hihoCoder#1120 小Hi小Ho的惊天大作战：扫雷・三 - 李舜阳 - 博客园

hihoCoder#1120 小Hi小Ho的惊天大作战：扫雷・三 - 李舜阳 - 博客园
http://hihocoder.com/problemset/problem/1120

提示：吾日三省吾身：能搜乎？好搜乎？怎搜乎？

输入

每个测试点（输入文件）存在多组测试数据。

每个测试点的第一行为一个整数Task，表示测试数据的组数。

在一组测试数据中：

第1行为2个整数N，M，表示迷宫的大小。

接下来的N行，每行M个整数，为一个矩阵A，用以描述整个迷宫，其中对于每一个格子A[i][j]，若A[i][j]=-1，则表示该格子没有被探明，若0<=a[i][j]<=8，则表示该格子已经被探明了，且数值代表该格子附近8个格子中的地雷数。<>

对于100%的数据，满足：5<=N、M<=10, -1<=a[i][j]<=8。<>

对于100%的数据，满足：符合数据描述的迷宫一定存在。

对于100%的数据，满足：迷宫中没有探明的格子的数量K<=10。<>

输出

对于每组测试数据，输出2个整数，分别为一定为地雷的未探明格子数和一定不为地雷的未探明格子数。

样例输入

2
10 10
  0  0  1  2 -1  1  0  0  1 -1
  1  1  1 -1  2  1  0  0  1  1
 -1  1  1  1  1  0  0  0  0  0
  1  1  0  0  0  1  1  1  0  0
  0  0  0  0  0  1 -1  1  0  0
  0  0  0  0  0  2  2  2  0  0
  0  0  0  0  0  1 -1  1  0 -1
  0  0  0  0  0  1  1  1  0  0
  0  0  0  0  1  1  1  0  0  0
 -1  0  0 -1  1 -1  1  0  0  0
9 10
  0  0  0  0  0 -1  0  0 -1  0
  0  0 -1  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  1  1  1
  0  0  0  0  0  1  2  3 -1  1
  0  0  0  0 -1  1 -1 -1  3  1
  1  1  0  0  0  1  3 -1  2  0
 -1  1  0  0  0  0  1  1 -1  0
  1  1  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0

样例输出

7 3
5 5

看上去非常复杂， 实际上是这一系列最简单的一步，本质上是个搜索过程，相比于前一道题，可以不用策略三，而且题目的数据规模超级小，所以暴力搜索就能过。
把尚未确定的点放在一个unsettled列表里，然后依次枚举每个点的情况：是地雷or不是地雷
优化方案一即：每次枚举后，使用规则一、规则二对列表里剩下的点进行判断，如果能直接判断出是不是地雷的就立即设置了，这样剩下的枚举位就少了。当然回溯的时候记得把这些拓展出来的也要一并回溯。
优化方案二即：周围已知地雷数少的点优先枚举。（这个优化没做）

于是问题来了：给出一张N*M（在经过三条规则的反复洗礼之后，N和M都并不会很大）的地图，其中的某些格子已经被探明，探明的格子中都标有一个数字，表明与它相邻的8个格子里的地雷数量，而没有探明的格子里可能会有一些地雷。

而现在小Ho需要做的便是：判断出这张地图中的哪些格子里一定是地雷，哪些格子里一定不是地雷。（在多解情况下，一定是地雷以及一定不是地雷的定义指的是在每一种可行解中都是地雷或者都不是地雷

 

 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 }

Read full article from hihoCoder#1120 小Hi小Ho的惊天大作战：扫雷・三 - 李舜阳 - 博客园