hihoCoder#1119 小Hi小Ho的惊天大作战：扫雷・二 - 李舜阳 - 博客园
http://hihocoder.com/problemset/problem/1119
http://hihocoder.com/problemset/problem/1119
给出一张N*M的地图，其中的某些格子已经被探明，探明的格子中都标有一个数字，表明与它相邻的8个格子里的地雷数量，而没有探明的格子里可能会有一些地雷。
现在小Ho仅仅知道如下三条规则：
1.如果某一个被探明的格子里所标的数字为0，那么它相邻的8个格子里的未探明格子被认作是一定不是地雷的格子。
2.如果某一个被探明的格子里所标的数字为K，且它相邻的8个格子里正好有K个没有探明的格子的话，则这K个没有探明的格子被认作是一定是地雷的格子。
3.如果某两个探明了的格子A和B，他们中标明的数字分别为P_A和P_B，且他们周围8个格子中没有探明的格子组成的集合分别为S_A和S_B，如果S_A包含S_B，且|S_A|-|S_B|=P_A-P_B，那么S_A-S_B中的所有格子，被认作是一定是地雷的格子。
而问题是：仅仅利用这三条规则，小Ho到底能判断出哪些没有探明的格子里一定是地雷，而哪些没有探明的格子里一定不是地雷呢？
值得注意的是：小Ho在这个问题上并不擅长，所以利用第一条规则导致一些未探明格子可以被判断为一定不是地雷，从而使得第二、三条规则可以作用的推理小Ho是做不出来的！所以每次规则的推导应当视作独立的，即不基于任何其他推导出的结论进行。
输入
每个测试点（输入文件）存在多组测试数据。
每个测试点的第一行为一个整数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<=2*10^2, -1<=A[i][j]<=8。<>
对于100%的数据，满足：符合数据描述的迷宫一定存在。
输出
对于每组测试数据，输出2个整数，分别为一定为地雷的未探明格子数和一定不为地雷的未探明格子数。
10 int N, M; 11 int map[SIZE][SIZE]; 12 int res[SIZE][SIZE]; 13 14 vector<pair<int, int> > unknown_neighbors(int i, int j) { 15 vector<pair<int, int> > nbs; 16 17 for (int ii = -1; ii < 2; ii++) 18 for (int jj = -1; jj < 2; jj++) { 19 int r = ii + i; 20 int c = jj + j; 21 if (r >= 0 && r < N && c >= 0 && c < M && (r != i || c != j) && map[r][c] < 0) 22 nbs.push_back(pair<int, int>(r, c)); 23 } 24 25 return nbs; 26 } 27 28 vector<pair<int, int> > known_counterparts(int i, int j) { 29 vector<pair<int, int> > cps; 30 31 for (int ii = -2; ii < 3; ii++) { 32 for (int jj = -2; jj < 3; jj++) { 33 int r = ii + i; 34 int c = jj + j; 35 if (r >= 0 && r < N && c >= 0 && c < M && (r != i || c != j) && map[r][c] >= 0) 36 cps.push_back(pair<int, int>(r, c)); 37 } 38 } 39 40 return cps; 41 } 42 43 vector<pair<int, int> > differ(vector<pair<int, int> > &a, vector<pair<int, int> > &b) { 44 vector<pair<int, int> > diff; 45 int count = 0; 46 47 for (auto pa : a) { 48 bool found = false; 49 for (auto pb : b) { 50 if (pb == pa) { 51 found = true; 52 count++; 53 break; 54 } 55 } 56 if (!found) 57 diff.push_back(pa); 58 } 59 60 if (count < b.size()) 61 diff.clear(); 62 63 return diff; 64 } 65 66 void merge_pos(int i, int j, int v) { 67 if (res[i][j] == -1 || res[i][j] == v) 68 res[i][j] = v; 69 else 70 res[i][j] = -2; 71 } 72 73 void solve() { 74 for (int i = 0; i < N; i++) 75 for (int j = 0; j < M; j++) { 76 if (map[i][j] == 0) { 77 vector<pair<int, int> > nbs = unknown_neighbors(i, j); 78 for (auto p : nbs) 79 merge_pos(p.first, p.second, 0); 80 } 81 else if (map[i][j] > 0) { 82 vector<pair<int, int> > nbs = unknown_neighbors(i, j); 83 if (nbs.size() == map[i][j]) { 84 for (auto p : nbs) 85 merge_pos(p.first, p.second, 1); 86 continue; 87 } 88 89 vector<pair<int, int> > cps = known_counterparts(i, j); 90 for (auto p : cps) { 91 vector<pair<int, int> > cp_nbs = unknown_neighbors(p.first, p.second); 92 if (nbs.size() <= cp_nbs.size() || map[i][j] <= map[p.first][p.second]) 93 continue; 94 vector<pair<int, int> > diff = differ(nbs, cp_nbs); 95 if ((int) (nbs.size() - cp_nbs.size()) == map[i][j] - map[p.first][p.second] && !diff.empty()) 96 for (auto dp : diff) 97 merge_pos(dp.first, dp.second, 1); 98 } 99 } 100 } 101 } 102 103 int main() { 104 int n; 105 106 cin >> n; 107 while (n--) { 108 cin >> N >> M; 109 for (int i = 0; i < N; i++) 110 for (int j = 0; j < M; j++) 111 cin >> map[i][j]; 112 memset(res, -1, SIZE * SIZE * sizeof(int)); 113 114 solve(); 115 116 int mine = 0; 117 int not_mine = 0; 118 119 for (int i = 0; i < N; i++) 120 for (int j = 0; j < M; j++) { 121 mine += (res[i][j] == 1 ? 1 : 0); 122 not_mine += (res[i][j] == 0 ? 1 : 0); 123 } 124 125 cout << mine << " " << not_mine << endl; 126 } 127 128 return 0; 129 }Read full article from hihoCoder#1119 小Hi小Ho的惊天大作战：扫雷・二 - 李舜阳 - 博客园
