题目内容
大意：在一个 5\times5 的棋盘上有 12 个白色的骑士和 12 个黑色的骑士，且有一个空位。在任何时候一个骑士都能按照骑士的走法（它可以走到和它横坐标相差为 1，纵坐标相差为 2 或者横坐标相差为 2，纵坐标相差为 1 的格子）移动到空位上。
给定一个初始的棋盘，怎样才能经过移动变成给定目标棋盘：
解题思路
该题明显是一个裸的搜索，但是暴搜铁定超时，再看到限制15步以内，于是想到打随机化使用来迭代加深。
同时这里还可以使用启发式搜索来进行剪枝，这里的估价函数可设为不在应有位置的骑士个数，然后每次枚举移动步数进行迭代加深即可。
像这种移动棋子的题选择移动空位会更好想一点，然后记得处理读入
代码（这个代码不知道为什么洛谷上没输出 LOJ 就 AC 了：
#include <cstdio>
#include <algorithm>
#include <cctype>
using namespace std;
const int tar[5][5]={//目标状态，1表示黑子，0表示白子，2表示空位
{1,1,1,1,1},
{0,1,1,1,1},
{0,0,2,1,1},
{0,0,0,0,1},
{0,0,0,0,0}
};
int board[5][5],idt;
const int fx[8]={1,1,-1,-1,2,2,-2,-2},fy[8]={2,-2,2,-2,1,-1,1,-1};//移动的数组
int h()//估价函数
{
int res=0;//统计多少枚棋子不在目标位置上
for(int i=0;i<5;i++)
for(int j=0;j<5;j++)
if(board[i][j]!=tar[i][j]) res++;
return res;
}
bool dfs(int x,int y,int d)//x，y为空位坐标，d为当前枚举的深度
{
if(d+h()>idt+1) return false;//如果估价函数显示这个限制深度铁定过不了就剪枝
if(!h()) return true;//如果已经到达目标状态，直接返回true
for(int k=0;k<8;k++)//枚举各个方向
{
int x1=x+fx[k],y1=y+fy[k];
if(x1>4||x1<0||y1>4||y1<0) continue;//判定越界
swap(board[x][y],board[x1][y1]);//否则交换棋子和空位的位置
if(dfs(x1,y1,d+1)) return true;//继续dfs，如果搜到了目标状态，返回
swap(board[x][y],board[x1][y1]);//回溯
}
return false;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)//毒瘤题目有很多组数据
{
int x0,y0;
for(int i=0;i<5;i++)
{
char s[5];
scanf("%s",s);
for(int j=0;j<5;j++)
{
if(isdigit(s[j])) board[i][j]=s[j]-'0';
if(s[j]=='*')
{
board[i][j]=2;
x0=i;
y0=j;
}
}
}
bool flag=0;
for(idt=1;idt<=15;idt++)//枚举深度
{
if(dfs(x0,y0,0)){flag=1;break;}//如果当前限制搜到了，那么停止
}
printf("%d\n",flag?idt:-1);
}
return 0;
}
留言