题目内容

洛谷2324

LOJ2151

大意:在一个 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;
}
最后修改日期:2020年3月1日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。