题目描述
围棋是起源于中国有悠久历史的策略性棋类游戏。它的规则如下：
1. 棋盘19*19。
2. 棋子分黑白两色，双方各执一色。
3. 下法：每次黑或白着一子于棋盘的空点上。棋子下定后，不再向其他点移动。
4. 棋子的气：一个棋子在棋盘上，与它相邻的空点是这个棋子的“气”（这里相邻是指两个点有公共边）。 相邻的点上如果有同色棋子存在，这些棋子就相互连接成一个不可分割的整体，气合并计算。
相邻的点上如果有异色棋子存在，此处的气便不存在。
如果棋子所在的连通块失去所有的气，即为无气之子，不能在棋盘上存在。
5. 提子：把无气之子清理出棋盘的手段叫“提子”。提子有二种：
1) 着子后，对方棋子无气，应立即提取对方无气之子。
2) 着子后，双方棋子都呈无气状态，应立即提取对方无气之子。
6. 禁着点：棋盘上的任何一空点，如果某方在此下子，会使该子立即呈无气状态，同时又不能提取对方的棋子，这个点叫做“禁着点”，该方不能在此下子。
7. 禁止全局同形：无论哪一方，在成功进行了着子、提子操作后，棋盘局面不能和任何之前的局面相同。
你要做的是：输入一些操作，从空棋盘开始模拟这些操作。
对于每一步，若结果不正确，则输出对应的miss并且忽略这个操作，并在最后输出棋盘的局面。
输入描述:
第一行，测试数据组数≤100
第二行，每组测试数据，执行的步数 n ≤ 2000
然后 n 行
B x y
W x y
(1 ≤ x ≤ 19,1 ≤ y ≤ 19)
其中，二元组 x,y 表示围棋棋盘上第 x 行第 y 列对应的点。
输入数据保证是黑白轮流下的。
输出描述:
多行
对于miss的情况，输出是哪一种错误格式，其中：
miss 1 表示下的位置已经有棋了
miss 2 表示违反规则6
miss 3 表示违反规则7
对于正常的操作，不用输出。
最后输出最终盘面。“B表示黑子，W表示白子，如果是空点的话，就输出'.'字符。”
示例1
输入
1 12 B 1 3 W 1 2 B 2 4 W 2 1 B 1 1 W 2 3 B 3 3 W 3 2 B 1 1 W 2 3 B 2 2 W 2 3
输出
miss 2 miss 2 miss 1 miss 3 .WB................ WB.B............... .WB................ ................... ................... ................... ................... ................... ................... ................... ................... ................... ................... ................... ................... ................... ................... ................... ...................
思路
一道模拟题。
模拟题重在如何实现，接下来挑出几个难以实现的地方说一说：
判断死活。
对于一块棋，有「气」就能活，没有「气」就会死。下面的 bool live(int, int, char) 处理了这个过程：
从一块棋的某个点开始找联通快，只有与自己相同的点才能相连。
另外，如果超出边界，按照围棋规则不算「气」；如果碰到不同色棋子，按照围棋规则同样也不算「气」。
如果碰到 . 就代表找到了至少一口气，就是暂时活棋。
落子。
考虑到围棋还有一个落子问题，也就是说不一定是落子之后自己没有「气」就会死，而是对方有「气」并且自己没有才会死。
这里采用的判断方法也很巧妙：
首先落下这颗子；
然后判断自己有没有气；
然后判断自己 四联通 的异色棋子会不会死；
如果自己可以“提”走别人，自己一定不会死（给我留出了「气」），如果自己提不走别人，别人堵住了我所有的「气」，我就会死。
哈希。
对于不能发生相同局面，这里可以考虑与 2. 难点建立联系，建立两个数组，一个是试错数组 now，另一个用于保存我之前的答案 old。
如果这里的数组 now 经过哈希之后有重复，就让 now ←\leftarrow← old，如果上述判断都没有问题，就让 old ←\leftarrow← now。
判断局面是否相同，直接哈希并把它扔到 set 里面判重一下就好了，这里采用的是双哈希，碰撞概率非常低。
AC
#include<set> #include<cstdio> #include<cstring> int init(){ char c = getchar(); int x = 0, f = 1; for (; c < '0' || c > '9'; c = getchar()) if (c == '-') f = -1; for (; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48); return x * f; } void print(int x){ if (x < 0) x = -x, putchar('-'); if (x > 9) print(x / 10); putchar(x % 10 + '0'); } const int N = (int) 2e1, dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1}; const int Buff1 = 131, Buff2 = 171, Mod1 = 998244353, Mod2 = (int) 1e9 + 7; char now[N][N], old[N][N]; void work(bool tp){ for (int i = 1; i < N; ++i) for (int j = 1; j < N; ++j) if (tp) old[i][j] = now[i][j]; else now[i][j] = old[i][j]; } int go(char ch){ if (ch == 'W') return 0; if (ch == 'B') return 1; return 2; } std::pair<int, int> Hash(){ int s1 = 0, s2 = 0; for (int i = 1; i < N; ++i) for (int j = 1; j < N; ++j) s1 = (s1 * 1ll * Buff1 + go(now[i][j])) % Mod1, s2 = (s2 * 1ll * Buff2 + go(now[i][j])) % Mod2; return std::make_pair(s1, s2); } std::set<std::pair<int, int> >set; bool vis[N][N]; bool live(int x, int y, char ch){ if (now[x][y] == '.') return 1; if (now[x][y] != ch) return 0; bool ans = 0; vis[x][y] = 1; for (int k = 0; k < 4; ++k) { int nx = x + dx[k], ny = y + dy[k]; if (nx < 1 || nx >= N || ny < 1 || ny >= N) continue; if (!vis[nx][ny]) ans |= live(nx, ny, ch); } return ans; } void clean(int x, int y, char ch){ now[x][y] = '.'; for (int k = 0; k < 4; ++k) { int nx = x + dx[k], ny = y + dy[k]; if (nx < 1 || nx >= N || ny < 1 || ny >= N) continue; if (now[nx][ny] == ch) clean(nx, ny, ch); } } int chk(char ch, int x, int y){ if (now[x][y] != '.') return 1; now[x][y] = ch; vis[x][y] = 1; bool ans = live(x, y, ch); for (int k = 0; k < 4; ++k) { int nx = x + dx[k], ny = y + dy[k]; if (!vis[nx][ny] && now[nx][ny] == 'W' + 'B' - ch && !live(nx, ny, 'W' + 'B' - ch)) ans |= 1, clean(nx, ny, 'W' + 'B' - ch); } if (!ans) return 2; if (set.count(Hash())) return 3; return 0; } void Print(const char*str){ for (int i = 0; str[i]; ++i) putchar(str[i]); } int main(){ int T = init(); while (T--) { set.clear(); for (int i = 1; i < N; ++i) for (int j = 1; j < N; ++j) now[i][j] = old[i][j] = '.'; int n = init(); for (int i = 1; i <= n; ++i) { memset(vis, 0, sizeof(vis)); char ch = 0; while (ch != 'B' && ch != 'W') ch = getchar(); int x = init(), y = init(); int tp = chk(ch, x, y); if (tp) Print("miss "), print(tp), putchar('\n'); else set.insert(Hash()); work(!tp); } for (int i = 1; i < N; ++i, putchar('\n')) for (int j = 1; j < N; ++j) putchar(now[i][j]); } }
