自动搬运

查看原文

来自洛谷，原作者为

	tiger2005 Failure, as usual.

搬运于2025-08-24 22:30:58，当前版本为作者最后更新于2021-05-09 10:24:39，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

建议读懂题目后再阅读下面的内容。

首先我们发现，可以使用一个 $3^9$ 大小的数字储存下一个井字棋状态。由于 $3^9 \leq 2*10^5$，所以我们可以考虑 $O(3^9N^2)$ 的方法。

考虑进行深度优先搜索。使用 bool hav[N][N][3**9] 记录下这个状态是否出现过（位置和井字棋的状态），防止重复搜索。如果没有被搜索过，首先判断这个位置上要不要填入棋子，需要的话改变状态。然后判断这个状态是否胜利，是的话记录并且退出。最后想四个方向进行搜索即可。

对于可行状态，可以直接转换成 3*3 的数组，然后暴力判断。建议先预处理出所有状态的可行性。

#pragma GCC optimize(2)
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>

using namespace std;
int N;
char Maz[30][100];
int pw[10];
int fang[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
bool dp[30][30][20010];
bool pd[20010];
bool isP[20010];
char mp[5][5];
inline bool isWin(int k){
	for(int i=1;i<=3;i++)
		for(int j=1;j<=3;j++){
			mp[i][j]=k%3;
			if(mp[i][j]==0)	mp[i][j]='.';
			else if(mp[i][j]==1)	mp[i][j]='M';
			else	mp[i][j]='O';
			k/=3;
		}
	string p="";
	for(int i=1;i<=3;i++){
		for(int j=1;j<=3;j++)
			p+=mp[i][j];
		if(p=="MOO" || p=="OOM")	return true;
		p="";
	}
	for(int i=1;i<=3;i++){
		for(int j=1;j<=3;j++)
			p+=mp[j][i];
		if(p=="MOO" || p=="OOM")	return true;
		p="";
	}
	for(int i=1;i<=3;i++)
		p+=mp[i][i];
	if(p=="MOO" || p=="OOM")	return true;
	p="";
	for(int i=1;i<=3;i++)
		p+=mp[i][4-i];
	if(p=="MOO" || p=="OOM")	return true;
	return false;
}
int Draw(int k,char q,int x,int y){
	x=3*x+y;
	int u=(k/pw[x])%3;
	if(u!=0)	return k;
	return k+(q=='M'?1:2)*pw[x];
}
int ans;
void dfs(int x,int y,int k){
	if(Maz[x][3*y+1]=='M' || Maz[x][3*y+1]=='O')
		k=Draw(k,Maz[x][3*y+1],Maz[x][3*y+2]-'1',Maz[x][3*y+3]-'1');
	if(dp[x][y][k])	return;
	dp[x][y][k]=true;
	if(isP[k]){
		ans+=!pd[k];
		pd[k]=true;
		return;
	}
	for(int i=0,xx,yy;i<4;i++){
		xx=x+fang[i][0],yy=y+fang[i][1];
		if(Maz[xx][3*yy+1]!='\0' && Maz[xx][3*yy+1]!='#')
			dfs(xx,yy,k);
	}
}
int main(){
	pw[0]=1;
	for(int i=1;i<=9;i++)	pw[i]=pw[i-1]*3;
	scanf("%d",&N);
	for(int i=1;i<=N;i++)
		scanf(" %s",Maz[i]+1);
	for(int i=0;i<pw[9];i++)	isP[i]=isWin(i);
	for(int i=1;i<=N;i++)
		for(int j=1;j<=N;j++)
			if(Maz[i][3*j+1]=='B')
				dfs(i,j,0);
	printf("%d",ans);
	return 0;
}