【宽搜】四子连棋 WikiOI 1004

最新推荐文章于 2024-05-26 10:00:00 发布

jiangzh7

最新推荐文章于 2024-05-26 10:00:00 发布

阅读量1.3k

点赞数

分类专栏：搜索

本文链接：https://blog.csdn.net/jiangzh7/article/details/8899712

版权

搜索专栏收录该内容

28 篇文章

订阅专栏

博客详细介绍了如何解决WikiOI 1004四子连棋问题，通过搜索算法寻找最少步数达到目标棋局。文章讨论了棋盘状态表示、状态设计、扩展合法方案及黑白交替行走的判断，并提供了C++实现的AC代码。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

WikiOI 1004 四子连棋

题目描述Description

在一个4*4的棋盘上摆放了14颗棋子，其中有7颗白色棋子，7颗黑色棋子，有两个空白地带，任何一颗黑白棋子都可以向上下左右四个方向移动到相邻的空格，这叫行棋一步，黑白双方交替走棋，任意一方可以先走，如果某个时刻使得任意一种颜色的棋子形成四个一线（包括斜线），这样的状态为目标棋局。

● ○ ●
○ ● ○ ●
● ○ ● ○
○ ● ○

从文件中读入一个4*4的初始棋局，黑棋子用B表示，白棋子用W表示，空格地带用O表示。

用最少的步数移动到目标棋局的步数。

BWBO

WBWB

BWBW

WBWO

5

这是我认为很好的一道搜索题（其实这一题的搜索不难，读题要仔细啊）

先说说地图怎么存，用0表示空格，1表示B，2表示W，所以最后可以看成一个16位的三进制数

首先，状态设计：step表示当前状态走的步数，map[][]表示当前状态的地图，hash表示把三进制数转为十进制数

然后每次当前状态出队后找到两个空白的点，然后分别向4个方向扩展出合法方案入队

入队的时候判重开hash表，最大好像是1亿多，所以开不下，所以我们用 stl 的map（或者set也行）

好了，这样做完，提交，很不幸，36分。。。。

仔细一看题，是黑白交替走，所以我们在状态上加一个last，表示当前出队的状态是哪个走的（1或2），然后判断一下和当前走的是否冲突就ok

判重的hash再加一维，表示是谁走的

提交，AC

测评情况（WikiOI）

C++ AC Code

/*http://blog.csdn.net/jiangzh7
By Jiangzh*/
#include<cstdio>
#include<cstdlib>
#include<queue>
#include<map>
using namespace std;
const int dx[]={1,-1,0,0};
const int dy[]={0,0,1,-1};

struct status{int hash,step,last;int map[6][6];}first;
queue<status> q;
map<int,bool> h[3];

int gethash(status a)//三进制hash值
{
	int res=0,k=1;
	for(int i=1;i<=4;i++)
		for(int j=1;j<=4;j++)
		{
			res+=a.map[i][j]*k;
			k*=3;
		}
	return res;
}

bool check(status a)
{
	for(int i=1;i<=4;i++)//行
	{
		int flag=1;
		for(int j=2;j<=4;j++)
			if(a.map[i][j-1]!=a.map[i][j]) flag=0;
		if(flag) return 1;
	}
	for(int j=1;j<=4;j++)//列
	{
		int flag=1;
		for(int i=2;i<=4;i++)
			if(a.map[i][j]!=a.map[i-1][j]) flag=0;
		if(flag) return 1;
	}
	//斜线
	if(a.map[1][1]==a.map[2][2] && a.map[2][2]==a.map[3][3] && a.map[3][3]==a.map[4][4]) return 1;
	if(a.map[1][4]==a.map[2][3] && a.map[2][3]==a.map[3][2] && a.map[3][2]==a.map[4][1]) return 1;
	return 0;
}

void move(status now,int x,int y,int k)
{
	status tmp=now;
	int tmpx=x+dx[k];
	int tmpy=y+dy[k];
	if(tmpx<1||tmpx>4) return;
	if(tmpy<1||tmpy>4) return;
	if(tmp.map[tmpx][tmpy]==tmp.last) return;//必须黑白交替走
	tmp.last=3-tmp.last;
	swap(tmp.map[x][y],tmp.map[tmpx][tmpy]);
	tmp.hash=gethash(tmp);
	tmp.step++;
	if(check(tmp)) {printf("%d\n",tmp.step);exit(0);}
	if(!h[tmp.last][tmp.hash])
	{
		h[tmp.last][tmp.hash]=1;
		q.push(tmp);
	}
}

void bfs()
{
	first.hash=gethash(first);
	first.last=1; q.push(first);
	first.last=2; q.push(first);
	while(!q.empty())
	{
		status now=q.front(); q.pop();
		int x1=-1,x2=-1,y1=-1,y2=-1;//两个空白的格子
		for(int i=1;i<=4;i++)
			for(int j=1;j<=4;j++)
				if(now.map[i][j]==0)
				{
					if(x1==-1&&y1==-1){x1=i;y1=j;}
					else{x2=i;y2=j;}
				}
		for(int k=0;k<4;k++)
		{
			move(now,x1,y1,k);
			move(now,x2,y2,k);
		}
	}
}

int main()
{
	freopen("1004.in","r",stdin);
	for(int i=1;i<=4;i++)
	{
		char s[10];scanf("%s",s);
		for(int j=0;j<4;j++)
		{
			if(s[j]=='B') first.map[i][j+1]=1;
			else if(s[j]=='W') first.map[i][j+1]=2;
		}
	}
	bfs();
	return 0;
}