题目大意是：在5×5的棋盘上有12个白子和12个黑子，另外有一个空格，白子或黑子可以按照骑士的行走方式走到空格位置。给定初始状态和目标状态，判断是否能够在10步（包含10步）以内达到目标状态。
典型的BFS，但是迭代加深的DFS效率同样很高，而且编程复杂度很低。在这里有一个优化：比如当前所做的搜索最大深度设定为maxdepth，比较当前状态和目标状态有多少处不同，结果假设为diff，则如果当前深度depth+diff/2>maxdepth，则停止当前搜索。比如有2处不同，那么最好情况就是2/2=1次转移到目标状态。
以下是我的代码：
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const char kTarget[5][5]={ {'1','1','1','1','1'},
{'0','1','1','1','1'},
{'0','0',' ','1','1'},
{'0','0','0','0','1'},
{'0','0','0','0','0'} };
const int dx[]={-2,-2,2,2,-1,1,-1,1},dy[]={-1,1,-1,1,-2,-2,2,2};
char r[5][5];
int ans;
bool success;
int Diff()
{
int re(0);
for(int i=0;i<5;i++)
for(int j=0;j<5;j++)
re+=(r[i][j]!=kTarget[i][j]);
return (re/2);
}
void dfs(int depth,int x,int y)
{
if(depth>=ans)
{
if(memcmp(r,kTarget,25*sizeof(char))==0)
success=true;
return;
}
//*
if(depth+Diff()>ans)
return;
//*/
for(int i=0;i<8 && !success;i++)
{
int newx(x+dx[i]),newy(y+dy[i]);
if(newx<0 || newx>= 5 || newy<0 || newy>=5)
continue;
swap(r[x][y],r[newx][newy]);
dfs(depth+1,newx,newy);
swap(r[x][y],r[newx][newy]);
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
#endif
int T;
scanf("%d",&T);
getchar();
while(T--)
{
int x,y;
for(int i=0;i<5;i++)
{
for(int j=0;j<5;j++)
{
scanf("%c",&r[i][j]);
if(r[i][j]==' ')
{
x=i;
y=j;
}
}
getchar();
}
success=false;
for(ans=0;ans<=10;ans++)
{
dfs(0,x,y);
if(success)
break;
}
if(success)
printf("Solvable in %d move(s).\n",ans);
else
printf("Unsolvable in less than 11 move(s).\n");
}
return 0;
}
posted on 2011-04-21 22:04
lee1r 阅读(1250)
评论(2) 编辑 收藏 引用 所属分类:
题目分类：搜索