P2346
查看原帖
P2346
768794
fuzhentao楼主2022/8/13 14:18

#include<bits/stdc++.h>
using namespace std;
char a[4][4];
int ans=10;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
bool check()//判断是否连成线
{
	for(int i=0;i<4;i++)
	{
		if(a[i][0]==a[i][1]&&a[i][1]==a[i][2]&&a[i][2]==a[i][3]) return true;
		if(a[0][i]==a[1][i]&&a[1][i]==a[2][i]&&a[2][i]==a[3][i]) return true;
	}
	if(a[0][0]==a[1][1]&&a[1][1]==a[2][2]&&a[2][2]==a[3][3]) return true;
	if(a[3][0]==a[2][1]&&a[2][1]==a[1][2]&&a[1][2]==a[0][3]) return true;
	return false;
}
void dfs(int k,int c)//k为现行步数,c为黑白棋
{
	if(k>ans) return;//找到最小步数就返回
	if(check()) ans=k-1;//如果联通就往小了找
	
	for(int i=0;i<4;i++)
	{
		for(int j=0;j<4;j++)
		{
			if(a[i][j]=='O')//移动空位
			{
				for(int p=0;p<4;p++)//四个方向
				{
					int x=i+dx[p],y=j+dy[p];
					if(x>=0&&x<4&&y>=0&&y<4&&(c==0&&a[x][y]=='B'||c==1&&a[x][y]=='W'))
					{
						swap(a[i][j],a[x][y]);
						dfs(k+1,1-c);
						swap(a[i][j],a[x][y]);
					}
				}
			}
		}
	}
}
int main()
{
	for(int i=0;i<4;i++)
	{
		for(int j=0;j<4;j++)
		{
			cin>>a[i][j];
		}
	}
	
	dfs(1,0);//黑棋
	dfs(1,1);//白棋
	printf("%d\n",ans);
	return 0;
}
//dfs爆搜
2022/8/13 14:18
加载中...