CodeDevil

链接：https://www.lydsy.com/JudgeOnline/problem.php?id=1054

【题意】

给定一个4*4的01矩阵和4*4的01目标矩阵，求原矩阵中的1经历多少次上下左右移动达到目标状态。

【题解】

傻*题，BFS+哈希判重就行了。

【代码】

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

 

int dir[4][2]={1,0,0,1,-1,0,0,-1};

bool des[5][5],inq[100100];

struct node

{

    bool a[5][5];

    int tms;

}q[100100];

 

int hashing(bool a[5][5])

{

    int i,j,k=1,s=0;

    for (i=1;i<=4;i++)

        for (j=1;j<=4;j++)

        {

            s+=k*a[i][j];

            k=k*2;

        }

    return s;

}

 

int main()

{

    string s;

    int x,y,tmp1,tmp2,i,j,k,i1,j1,f,r;

    for (i=1;i<=4;i++)

    {

        cin>>s;

        for (j=1;j<=4;j++)

            q[1].a[i][j]=s[j-1]-48;

    }

    for (i=1;i<=4;i++)

    {

        cin>>s;

        for (j=1;j<=4;j++)

            des[i][j]=s[j-1]-48;

    }

    tmp1=hashing(q[1].a),tmp2=hashing(des);

    if (tmp1==tmp2)

    {

        printf("0\n");

        return 0;

    }

    inq[tmp1]=true;

    f=0,r=1;

    while (f<r)

    {

        f++;

        for (i=1;i<5;i++)

            for (j=1;j<5;j++)

                if (q[f].a[i][j])

                    for (k=0;k<4;k++)

                    {

                        int x=i+dir[k][0],y=j+dir[k][1];

                        if (!q[f].a[x][y] && x>0 && x<5 && y>0 && y<5)

                        {

                            q[f].a[x][y]=1;q[f].a[i][j]=0;

                            int tmp=hashing(q[f].a);

                            if (!inq[tmp])

                            {

                                r++;

                                for (i1=1;i1<5;i1++)

                                    for (j1=1;j1<5;j1++)

                                        q[r].a[i1][j1]=q[f].a[i1][j1];

                                q[r].tms=q[f].tms+1;

                                inq[tmp]=true;

                                if (tmp==tmp2)

                                {

                                    printf("%d\n",q[r].tms);

                                    return 0;

                                }

                            }

                            q[f].a[x][y]=0;q[f].a[i][j]=1;

                        }

                    }

    }

    return 0;

}