題目大意是：在5×5的棋盤上有12個(gè)白子和12個(gè)黑子，另外有一個(gè)空格，白子或黑子可以按照騎士的行走方式走到空格位置。給定初始狀態(tài)和目標(biāo)狀態(tài)，判斷是否能夠在10步（包含10步）以內(nèi)達(dá)到目標(biāo)狀態(tài)。
典型的BFS，但是迭代加深的DFS效率同樣很高，而且編程復(fù)雜度很低。在這里有一個(gè)優(yōu)化：比如當(dāng)前所做的搜索最大深度設(shè)定為maxdepth，比較當(dāng)前狀態(tài)和目標(biāo)狀態(tài)有多少處不同，結(jié)果假設(shè)為diff，則如果當(dāng)前深度depth+diff/2>maxdepth，則停止當(dāng)前搜索。比如有2處不同，那么最好情況就是2/2=1次轉(zhuǎn)移到目標(biāo)狀態(tài)。
以下是我的代碼：
#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 閱讀(1266)
評論(2) 編輯 收藏 引用 所屬分類:
題目分類：搜索