题解 P3930 【SAC E#1 - 一道大水题 Knight】

未见堇开 · 2019-11-10 21:56:51 · 题解

这里是一个学DFS学傻了，忘了如何写BFS的蒟蒻的记搜题解。

看到最小步数，考虑IDDFS。

棋子的攻击范围可以直接覆盖并叠加，在吃掉棋子后暴力消除覆盖即可。

直接记录剩余i步时在(x,y)能否杀王以实现记搜，空间开销不大，可以接受。

代码很长，请酌情阅读。

#include<cstdio>
#include<cstring>
#define reg register
#define MAXN 60
using namespace std;

const int dx[8]={1,1,2,2,-1,-1,-2,-2};
const int dy[8]={2,-2,1,-1,2,-2,1,-1};
int ban[MAXN][MAXN],dp[MAXN][MAXN][505];//dp记搜，ban记录覆盖情况
char map[MAXN][MAXN];
int n,x,y,ex,ey;

inline bool inmap(char ch)
{return(ch=='.'||ch=='O'||ch=='C'||ch=='K'||ch=='B'||ch=='Q'||ch=='X'||ch=='P');}

inline bool out(int x,int y)//越界
{return(x<1||x>n||y<1||y>n);}

inline int trans(char ch)
{
    if(ch=='C')
        return(1);
    if(ch=='K')
        return(4);
    if(ch=='X')
        return(5);
    if(ch=='B')
        return(2);
    if(ch=='Q')
        return(3);
    if(ch=='P')
        return(6);
    return(7);
}

inline void cover(int type,int px,int py,int val)
{
    if(type>6)
        return;
    if(type==6)//兵
    {
        if(!out(px+1,py-1))
            ban[px+1][py-1]+=val;
        if(!out(px+1,py+1))
            ban[px+1][py+1]+=val;
        return;
    }
    if(type==5)//王
    {
        if(!out(px+1,py-1))
            ban[px+1][py-1]+=val;
        if(!out(px+1,py+1))
            ban[px+1][py+1]+=val;
        if(!out(px+1,py))
            ban[px+1][py]+=val;
        if(!out(px-1,py+1))
            ban[px-1][py+1]+=val;
        if(!out(px-1,py-1))
            ban[px-1][py-1]+=val;
        if(!out(px-1,py+1))
            ban[px-1][py]+=val;
        if(!out(px,py-1))
            ban[px][py-1]+=val;
        if(!out(px,py+1))
            ban[px][py+1]+=val;
        return;
    }
    if(type==4)//马
    {
        if(!out(px-1,py-2))
            ban[px-1][py-2]+=val;
        if(!out(px-1,py+2))
            ban[px-1][py+2]+=val;
        if(!out(px+1,py-2))
            ban[px+1][py-2]+=val;
        if(!out(px+1,py+2))
            ban[px+1][py+2]+=val;
        if(!out(px-2,py-1))
            ban[px-2][py-1]+=val;
        if(!out(px-2,py+1))
            ban[px-2][py+1]+=val;
        if(!out(px+2,py-1))
            ban[px+2][py-1]+=val;
        if(!out(px+2,py+1))
            ban[px+2][py+1]+=val;
    }
    for(reg int i=1;i<=n;i++)//车、象和后，暴力覆盖
    {
        if(type&1)
        {
            if(!out(px-i,py))
                ban[px-i][py]+=val;
            if(!out(px+i,py))
                ban[px+i][py]+=val;
            if(!out(px,py-i))
                ban[px][py-i]+=val;
            if(!out(px,py+i))
                ban[px][py+i]+=val;
        }
        if(type&2)
        {
            if(!out(px-i,py-i))
                ban[px-i][py-i]+=val;
            if(!out(px+i,py+i))
                ban[px+i][py+i]+=val;
            if(!out(px+i,py-i))
                ban[px+i][py-i]+=val;
            if(!out(px-i,py+i))
                ban[px-i][py+i]+=val;
        }
    }
    return;
}

bool dfs(int rest,int px,int py)
{
    if(rest==0)
        return(px==ex&&py==ey);
    if(dp[px][py][rest])
        return(dp[px][py][rest]==2);
    bool res=false;
    for(reg int i=0;i<8;i++)
    {
        int qx=px+dx[i],qy=py+dy[i];
        if(out(qx,qy)||(ban[qx][qy]&&(qx!=ex||qy!=ey)))
            continue;
        char tmp=map[qx][qy];
        if(tmp!='.')
            map[qx][qy]='.';
        cover(trans(tmp),qx,qy,-1);
        res|=dfs(rest-1,qx,qy);
        cover(trans(tmp),qx,qy,1);
        map[qx][qy]=tmp;
        if(res)
            return(dp[px][py][rest]=2,true);
    }
    return(dp[px][py][rest]=res?2:1,res);
}

int main()
{
    while(scanf("%d",&n)!=EOF)//多组数据
    {
        memset(ban,0,sizeof(ban));
        memset(dp,0,sizeof(dp));
        for(reg int i=1,j=0;i<=n;i++)
        {
            char ch=getchar();
            while(!inmap(ch))
                ch=getchar();
            map[i][++j]=ch;
            if(ch=='O')
                x=i,y=j;
            if(ch=='X')
                ex=i,ey=j;
            cover(trans(ch),i,j,1);//覆盖
            if(j!=n)
                --i;
            else
                j=0;//结束本行读入
        }
        if(ban[x][y])
        {
            puts("-1");
            continue;
        }
        reg int res=1;
        for(;res<=500;++res)//IDDFS
        {
            if(dfs(res,x,y))
                break;
        }
        printf("%d\n",res==500?-1:res);
    }
    return(0);
}