题解 P2324 【[SCOI2005]骑士精神】

木木！ · 2019-09-22 16:29:29 · 题解

看dalao都用的是ID-DFS、IDA*或者A*，这里贴一篇双向ID-DFS的题解。

蒟蒻首先用的是单向ID-DFS，然后毫无悬念地T飞，只拿了十分。然后发现样例的第一个部分（7）跑得飞快，第二个部分（-1）慢到我以为死循环了。试着输出ID-DFS的层级，发现1-7这几层几乎瞬间跑完，然后从9开始越来越慢，14的时候就已经要两秒了。

双向ID-DFS的理念和双向BFS差不多，都是通过双向搜索来减少搜索树的大小。双向ID-DFS就是两个方向交替ID-DFS，每个方向8层，末一层在map里记录一下，相遇时就得到了答案。

最后因为骚操作比较多，搓了一个小时，跑了2.5s多，然后我看着别人1KB 500ms的IDA*代码思考人生。

附AC代码：

#include <map>
#include <cstdio>
using namespace std;

char gc()
{
    char c;
    while((c=getchar())!='0' && c!='1' && c!='*')
    {
        ;
    }
    return c;
}

int gox[] = {1,2,-2,-1,-1,-2,2,1};
int goy[] = {2,1,1,2,-2,-1,-1,-2};

int csed[6][6] = {{},{0,1,1,1,1,1},{0,0,1,1,1,1},{0,0,0,0,1,1},{0,0,0,0,0,1},{0,0,0,0,0,0}};

map<int,int> edmmp;
map<int,int> bgmmp;

int bg[6][6];
int ed[6][6];

template<typename T> int bcode(T board) //骚操作，因为发现用不了int[][]和int**以及int(*)[6]，于是干脆弃疗
{
    int res = 0;
    for(int i=1; i<=5; ++i)
    {
        for(int j=1; j<=5; ++j)
        {
            res <<= 1;
            res += board[i][j];
        }
    }
    return res;
}

inline int lcode(int x,int y)
{
    return (x-1)*5+y-1;
}

template<typename T> bool cregis(int wx,int wy,T board,map<int,int>& cmmp,map<int,int>& rmmp)
{
    int chk = cmmp[bcode(board)];

    if(chk&(1<<lcode(wx,wy)))
    {
        return true;
    }

    int& x = rmmp[bcode(board)];

    if(x)
    {
        x |= 1<<lcode(wx,wy);
    }
    else
    {
        x = 1<<lcode(wx,wy);
    }

    return false;
}

template<typename T> bool id_dfs(int life,int wx,int wy,T board,map<int,int>& cmmp,map<int,int>& rmmp)
{
    if(!life)
    {
        return cregis(wx,wy,board,cmmp,rmmp);
    }
    for(int i=0; i<8; ++i)
    {
        int nxtwx = wx+gox[i];
        int nxtwy = wy+goy[i];

        if(nxtwx>0&&nxtwx<=5&&nxtwy>0&&nxtwy<=5)
        {   
            swap(board[wx][wy],board[nxtwx][nxtwy]);
            if(id_dfs(life-1,nxtwx,nxtwy,board,cmmp,rmmp)) return true;
            swap(board[wx][wy],board[nxtwx][nxtwy]);
        }
    }
    return false;
}

int main()
{
    int t;
    scanf("%d",&t);
    for(int kkk=1; kkk<=t; ++kkk)
    {
        bgmmp.clear(); //记得初始化
        edmmp.clear();
        for(int i=1; i<=5; ++i)
        {
            for(int j=1; j<=5; ++j)
            {
                ed[i][j] = csed[i][j];
            }
        }

        int bwx,bwy;
        for(int i=1; i<=5; ++i)
        {
            for(int j=1; j<=5; ++j)
            {
                bg[i][j] = gc();
                if(bg[i][j]=='*')
                {
                    bwx = i;
                    bwy = j;
                    bg[i][j] = 0;
                }
                else
                {
                    bg[i][j] ^= '0';
                }
            }
        }

        id_dfs(0,3,3,ed,bgmmp,edmmp);
        if(id_dfs(0,bwx,bwy,bg,edmmp,bgmmp)) //特判
        {
            printf("0\n");
            goto ed;
        }
        for(int i=1; i<=15; ++i)
        {
            if(i&1) //交替进行
            {
                if(id_dfs((i+1)>>1,3,3,ed,bgmmp,edmmp))
                {
                    printf("%d\n",i);
                    goto ed;
                }
            }
            else
            {
                if(id_dfs(i>>1,bwx,bwy,bg,edmmp,bgmmp))
                {
                    printf("%d\n",i);
                    goto ed;
                }
            }
        }

        printf("-1\n");

        ed:;
    }
}