题解 | #围棋#

题意：

围棋是起源于中国有悠久历史的策略性棋类游戏。它的规则如下：

1. 棋盘19*19。
2. 棋子分黑白两色，双方各执一色。
3. 下法：每次黑或白着一子于棋盘的空点上。棋子下定后，不再向其他点移动。
4. 棋子的气：一个棋子在棋盘上，与它相邻的空点是这个棋子的“气”（这里相邻是指两个点有公共边）。 相邻的点上如果有同色棋子存在，这些棋子就相互连接成一个不可分割的整体，气合并计算。 相邻的点上如果有异色棋子存在，此处的气便不存在。 如果棋子所在的连通块失去所有的气，即为无气之子，不能在棋盘上存在。
5. 提子：把无气之子清理出棋盘的手段叫“提子”。提子有二种：

1. 着子后，对方棋子无气，应立即提取对方无气之子。
2. 着子后，双方棋子都呈无气状态，应立即提取对方无气之子。

6. 禁着点：棋盘上的任何一空点，如果某方在此下子，会使该子立即呈无气状态，同时又不能提取对方的棋子，这个点叫做“禁着点”，该方不能在此下子。
7. 禁止全局同形：无论哪一方，在成功进行了着子、提子操作后，棋盘局面不能和任何之前的局面相同。

你要做的是：输入一些操作，从空棋盘开始模拟这些操作。 对于每一步，若结果不正确，则输出对应的miss并且忽略这个操作，并在最后输出棋盘的局面。

解：（模拟题，直接分析模拟的流程）

19*19的棋盘，双方轮流下棋。

在以下几种情况下，这一步是下不了的，直接忽略掉这步操作

1.当前的格子里面已经有棋子，返回miss 1

2.放上棋子之后，我方棋子（没气）并且对方（有气）

或者说我方棋子没气，并且不能抽取对方的气

3.棋盘状态重复

这样子的话，我们就只需要拆解成几个部分解决

1、每次用临时棋盘存储当前进行的未知合法与否的状态

2、放棋子之后查看这个棋子所在联通块是否有气，以及四个相邻格子上的异色棋子是否有气

3、把棋盘状态用hash映射在set里面判断状态是否重复。

#include<bits/stdc++.h>
using namespace std;

const int N = 20;
typedef unsigned long long ull;
const ull base = 2331;
char c[N][N],w[N][N];
char op;
int n,t,x,y;
set<ull>se;

void init()
{
	for(int i = 1;i <= 19; ++i)
		for(int j = 1;j <= 19; ++j)
			c[i][j] = '.';
	se.clear();
}

void copy(int x)
{
	for(int i = 1;i <= 19; ++i)
		for(int j = 1;j <= 19; ++j)
			if(!x) w[i][j] = c[i][j];
				else c[i][j] = w[i][j];
}

int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};
bool vis[N][N];

int get_num(int x,int y)
{
	int s = 0;
	for(int i = 0;i < 4; ++i)
	{
		int xx = x + dx[i];
		int yy = y + dy[i];
		if(xx < 1 || yy < 1 || xx > 19 || yy > 19 || vis[xx][yy]) continue;
		if(w[xx][yy] == '.') s++;
		if(w[xx][yy] == w[x][y]) 
		{
			vis[xx][yy] = 1;
			s += get_num(xx,yy);
		}
	}
	return s;
}

int check(int x,int y)
{
	memset(vis,0,sizeof(vis));
	return get_num(x,y);
}

void clean(int x,int y,char ch)
{
	w[x][y] = '.';
	for(int i = 0;i < 4; ++i)
	{
		int xx = x + dx[i];
		int yy = y + dy[i];
		if(xx < 1 || yy < 1 || xx > 19 || yy > 19 
		   || w[xx][yy] == '.' || w[xx][yy] != ch) continue;
		clean(xx,yy,ch);
	}
}

ull Hash()
{
	ull res = 0;
	for(int i = 1;i <= 19; ++i)
		for(int j = 1;j <= 19; ++j)
			res = res * base + w[i][j];
	return res;
}

int work()
{
	copy(0);
	if(w[x][y] != '.') return 1;
	w[x][y] = op;
	int s = 0;
	for(int i = 0;i < 4; ++i)
	{
		int xx = x + dx[i];
		int yy = y + dy[i];
		if(xx < 1 || yy < 1 || xx > 19 || yy > 19 || 
		   w[xx][yy] == '.' || w[x][y] == w[xx][yy]) continue;
		if(check(xx,yy) == 0) s++,clean(xx,yy,w[xx][yy]);
	}
	if(check(x,y) == 0 && !s) return 2;	
	if(se.find(Hash()) != se.end()) return 3;
	se.insert(Hash());
	copy(1);
	return 0;	
}

void solve()
{
	cin>>n;
	copy(0);
	se.insert(Hash());
	for(int i = 1;i <= n; ++i)
	{
		cin>>op>>x>>y;
		int k = work();
		if(k) cout<<"miss "<<k<<'\n';
	}
	for(int i = 1;i <= 19; ++i)
    {
		for(int j = 1;j <= 19; ++j)
			cout<<c[i][j];
        cout<<'\n';
    }
}

int main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin>>t;
	while(t--)
	{
		init();
		solve();
	}
	return 0;
}