【日常学习】【迭代加深搜索+哈希】codevs1004 四子连棋题解

快来打我* 2022-08-04 11:49 171阅读 0赞

题目描述 Description

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

输入描述 Input Description

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

输出描述 Output Description

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

样例输入 Sample Input

BWBO  
WBWB  
BWBW  
WBWO

样例输出 Sample Output

经历了六个小时的努力，这道题目终于AC了···看题解上的反应，刘哥小时不算个例，大有人在啊，连黄学长也花了一个多小时。不过，要是NOIP赛场上碰到这道题，我还不得调试到歇菜？所以说，还是要好好增强代码能力，避免细节上的失误。

是的，这道题目看似简单，但是细节非常多，需要仔细注意。

先说一下思路吧！

一看当然是直接搜，那么采用深搜还是广搜呢？通常情况下，我们考虑广搜，因为这道题要求球最少步数，且很难剪枝，深搜不起效果。那么为什么我们采用了迭代加深搜索呢？首先要考虑的是，广搜有可能爆空间（这道题目并不会爆空间，但是通常使用迭代加深都是因为广搜可能超出空间，而迭代加深本质上就是一种时间换空间的策略，它的复杂度比深搜要高很多，按完全二叉树算要高一倍，但是空间消耗少）。而我们在这里考虑的主要是：黑白棋子都可能先走，如果广搜我个人可能实现上有困难，因为要交替入队。这道题我成功地写出ID，某种意义上是撞大运了而已，ID比广搜快很多大概也和数据有关，正解还应当是广搜。

我们每个阶段（就是步数限制）搜索两次，第一次黑棋先行，第二次白棋先行。每次搜索又循环两次，因为有两个空格。

这道题的启发之一是：不必将数组作为参数传递到函数中，只需作为全局变量，每次修改后回溯即可。我传递了两个参数，一个是当前层数，其实如果把我的好这个也不必传递，但传递了会好写一些；另一个是这一步该走黑棋还是白棋，不难看出，这个也可以不传递。也就是说什么参数都不传递也可以。

如何判断是否达到目标状态？参考黄学长的做法：

bool equ(int &a1,int &a2,int &a3,int &a4)
 {
 if (a1!=a2||a2!=a3||a3!=a4||a4!=a1) return 0;
 	return 1;
 }
 
 inline bool check()
 {
 for(int i=0;i<4;i++)
 {
 if(equ(e.a[i][0],e.a[i][1],e.a[i][2],e.a[i][3]))return 1;
 if(equ(e.a[1][i],e.a[2][i],e.a[3][i],e.a[0][i]))return 1;
 }
 if(equ(e.a[1][1],e.a[2][2],e.a[3][3],e.a[0][0]))return 1;
 if(equ(e.a[0][3],e.a[1][2],e.a[2][1],e.a[3][0]))return 1;
 return 0;
 }

这里，黄学长存图的坐标是1-4，而我是0-3，可真是坑死我了= =一开始没注意，忘了修改，以至于单步了很多遍才发现···

那么，如何判断状态是否重复呢？之前我们用了set，然而据里奥神犇介绍，不开O2优化的set要比哈希表慢一半（当然了，哈希表只是数组和取模而已）。因此我们尝试了哈希表。这篇文章之所以是“日常学习”，正是因为这是哈希表的第一次出现。

哈希的代码很简单：

</pre>首先开一个4000000的bool数组hash<pre name="code" class="cpp">inline bool gethash(const node &e,const int &depth)
 {
 	int va=0;
 	for (int i=0;i<4;i++)
 	{
 		for (int j=0;j<4;j++)
 		{
 			va=va*3+e.a[i][j];
 		}
 	}
 	va%=3733799;
 	if (hash[va])) return false;
 	hash[va]=true;
 	return true;
 }

上面是我最初写的哈希表。这个代码拿到广搜里可以直接用，但是迭代加深不行！为什么呢？

考虑这样一种情况：**某个方向上，深度限制为5，我们在第四步找到了这个状态，打上哈希，之后发现这个方向上并无正解。我们又向另一个方向走，发现第二步又走到了这个状态，然而它已经被打上哈希了，因此我们跳过。但实际上，从这个状态走三步后正是目标状态，应当输出5。**这可怎么办呢？

我们仔细观察，为什么广搜不会出现这种情况？因为广搜是严格按层扩展，如果这个状态被找到一定是在最近的位置（第二步）被找到。因此我们可以设一个数组have，存储被哈希过的数是在第几步被找到的。再次遇到该状态时，判断一下是否当前走的步数比have数组中存的步数少，如果少，我们把它继续向下搜索。

修改后的代码是这样的：

inline bool gethash(const node &e,const int &depth)
 {
 	int va=0;
 	for (int i=0;i<4;i++)
 	{
 		for (int j=0;j<4;j++)
 		{
 			va=va*3+e.a[i][j];
 		}
 	}
 	va%=3733799;
 	if (hash[va]&&(have[va]<=depth)) return false;
 	hash[va]=true;
 	have[va]=depth;
 	return true;
 }

这里还应注意的一个问题是， **迭代加深搜索每次加深都应该将哈希表清空！！！**

这是因为，迭代加深每次都是从第一层开始搜，如果不清空，一开始的状态在上一次搜索时已经被哈希，就无处可搜了。

那么代码君奉上：

//codevs1004 ËÄ×ÓÁ¬Æå DFS+ID
 //copyright by ametake
 
 #include
 
 
 #include
 
 
 #include
 
 
 using namespace std;
 
 const int xx[4]={0,1,0,-1};
 const int yy[4]={1,0,-1,0};
 
 struct node
 {
 	int a[4][4];
 	int ax,ay,bx,by;//Á½¸ö¿Õ¸ñ ÁíÍâ ºÚ1°×2¿Õ0 
 }e;
 
 int have[4000000]={0};
 bool hash[4000000]={false};
 bool ok=false;
 int k;
 
 inline bool gethash(const node &e,const int &depth)
 {
 	int va=0;
 	for (int i=0;i<4;i++)
 	{
 		for (int j=0;j<4;j++)
 		{
 			va=va*3+e.a[i][j];
 		}
 	}
 	va%=3733799;
 	if (hash[va]&&(have[va]<=depth)) return false;
 	hash[va]=true;
 	have[va]=depth;
 	return true;
 }
 
 bool equ(int &a1,int &a2,int &a3,int &a4)
 {
 if (a1!=a2||a2!=a3||a3!=a4||a4!=a1) return 0;
 	return 1;
 }
 
 inline bool check()
 {
 for(int i=0;i<4;i++)
 {
 if(equ(e.a[i][0],e.a[i][1],e.a[i][2],e.a[i][3]))return 1;
 if(equ(e.a[1][i],e.a[2][i],e.a[3][i],e.a[0][i]))return 1;
 }
 if(equ(e.a[1][1],e.a[2][2],e.a[3][3],e.a[0][0]))return 1;
 if(equ(e.a[0][3],e.a[1][2],e.a[2][1],e.a[3][0]))return 1;
 return 0;
 }
 
 void search(int depth,int black)
 {
 	if (depth>k) return;
 	for (int i=0;i<4;i++)//×¢ÒâÒªÖØ¸´Ò»±é£¬ÒòÎªÓÐÁ½¸ö¿Õ¸ñ 
 	{
 		int nx=e.ax+xx[i];
 		int ny=e.ay+yy[i];
 		if (nx<0||nx>3||ny<0||ny>3) continue;
 		if (e.a[nx][ny]!=black) continue;
 		swap(e.a[nx][ny],e.a[e.ax][e.ay]);
 		if (gethash(e,depth))
 		{
 			if (depth==k)
 			{
 				if (check())
 				{
 					ok=true;/*
 					for (int i=0;i<4;i++)
 	 {
 		 for (int j=0;j<4;j++)
 		 {
 			 printf("%d ",e.a[i][j]);
 		 }
 		 printf("\n");
 	 }*/
 					swap(e.a[nx][ny],e.a[e.ax][e.ay]);
 					break;
 				}
 		 }
 		 int flag=1;
 		 if (black==1) flag++;
 		 e.ax=nx;
 		 e.ay=ny;
 		 search(depth+1,flag);
 		 e.ax-=xx[i];
 		 e.ay-=yy[i];
 		}
 		swap(e.a[nx][ny],e.a[e.ax][e.ay]);
 		
 		if (ok) return;
 	}
 	for (int i=0;i<4;i++)//×¢ÒâÒªÖØ¸´Ò»±é£¬ÒòÎªÓÐÁ½¸ö¿Õ¸ñ 
 	{
 		int nx=e.bx+xx[i];
 		int ny=e.by+yy[i];
 		if (nx<0||nx>3||ny<0||ny>3) continue;
 		if (e.a[nx][ny]!=black) continue;
 		swap(e.a[nx][ny],e.a[e.bx][e.by]);
 		if (gethash(e,depth))
 		{
 			if (depth==k)
 			{
 				if (check())
 				{
 					ok=true;
 					swap(e.a[nx][ny],e.a[e.bx][e.by]);
 				 break;
 				}
 		 }
 		 int flag=1;
 		 if (black==1) flag++;
 		 e.bx=nx;
 		 e.by=ny;
 		 search(depth+1,flag);
 		 e.bx-=xx[i];
 		 e.by-=yy[i];
 		}
 		swap(e.a[nx][ny],e.a[e.bx][e.by]);
 		if (ok) return;
 	}
 }
 
 int main()
 {
 	freopen("1.txt","r",stdin);
 	char s[5];
 	bool have=false;
 	for (int i=0;i<4;i++)
 	{
 		scanf("%s",s);
 		for (int j=0;j<4;j++)
 		{
 			int x;
 			if (s[j]=='B') x=1;
 			else if (s[j]=='W') x=2;
 			else
 			{
 				x=0;
 				if (!have)
 				{
 					e.ax=i;
 					e.ay=j;
 					have=true;
 				}
 				else 
 				{
 					e.bx=i;
 					e.by=j;
 				}
 			}
 			e.a[i][j]=x;
 		}
 }
 for (k=1;k<=10;k++)
 {
 	memset(hash,false,sizeof(hash));
 	search(1,1);//kÊÇ²ãÊýÏÞÖÆ£¬2±íÊ¾ÕâÒ»²½¸Ã×ß°×1±íÊ¾ÕâÒ»²½¸Ã×ßºÚ
 		if (!ok)search(1,2);//1±íÊ¾µ±Ç°ËÑµÄÊÇµÚ1²ã 
 		if (ok)
 		{
 			printf("%d\n",k);
 			break;
 	 }
 }
 if (!ok) printf("why------");
 return 0;
 }

今天中午知道了很多。originlab君，你的帮助真的让我非常感激，素日一直默默奉献，而且我今天凌晨给你发的私信竟然那么快就收到回信，介绍的很详细，实在感动。今天才知道电骡，以及电骡用户们，一群坚持着的人们。我发现互联网的神秘面纱正在慢慢揭开，让我看到一个全新的世界。所以还是要好好学，努力学才能做一个合格的技术宅（¯﹃¯）

——遗民泪尽胡尘里，南望王师又一年