一道模拟题。

模拟题重在如何实现，接下来挑出几个难以实现的地方说一说：

  1. 判断死活。

对于一块棋，有「气」就能活，没有「气」就会死。下面的 bool live(int, int, char) 处理了这个过程：

  • 从一块棋的某个点开始找联通快，只有与自己相同的点才能相连。
  • 另外，如果超出边界，按照围棋规则不算「气」；如果碰到不同色棋子，按照围棋规则同样也不算「气」。
  • 如果碰到 . 就代表找到了至少一口气，就是暂时活棋。
  1. 落子。

考虑到围棋还有一个落子问题，也就是说不一定是落子之后自己没有「气」就会死，而是对方有「气」并且自己没有才会死。

这里采用的判断方法也很巧妙：

  • 首先落下这颗子；
  • 然后判断自己有没有气；
  • 然后判断自己 四联通 的异色棋子会不会死；

如果自己可以“提”走别人，自己一定不会死（给我留出了「气」），如果自己提不走别人，别人堵住了我所有的「气」，我就会死。

  1. 哈希。

对于不能发生相同局面，这里可以考虑与 2. 难点建立联系，建立两个数组，一个是试错数组 now，另一个用于保存我之前的答案 old。

如果这里的数组 now 经过哈希之后有重复，就让 now ←\leftarrow old，如果上述判断都没有问题，就让 old ←\leftarrow now。

判断局面是否相同，直接哈希并把它扔到 set 里面判重一下就好了，这里采用的是双哈希，碰撞概率非常低。

#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]);
	}
}