2284 - 【宽搜入门】8数码难题

Solution C++

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
using namespace std;
const int dx[4]={0,-1,0,1};
const int dy[4]={-1,0,1,0};
struct node
{
    int a[4][4],x,y,dep;
}list[400000]; int head,tail;
bool tf(node n1,node n2)
{
    int x,y;
    for(x=1;x<=3;x++)
       for(y=1;y<=3;y++)
           if( n1.a[x][y]!= n2.a[x][y])
              return false;
    return true;
}
bool check(node tno)
{
    int i;
    for(i=1;i<=tail;i++)
        if(  tf( list[i],tno) ==true)
           return true;
    return false;
}
int main()
{
    int i,j,tt;
     for(i=1;i<=3;i++)
        for(j=1;j<=3;j++)
        {
           scanf("%d", &list[1].a[i][j]);
           if(  list[1].a[i][j]==0) { list[1].x=i;list[1].y=j;}
        }
     list[1].dep=1;

     for(i=1;i<=3;i++)
        for(j=1;j<=3;j++)
           scanf("%d", &list[0].a[i][j]);
     head=1;tail=1;
     node tno;

     while( head<=tail)
     {
        bool bk=false;
        for(i=0;i<=3;i++)
        {
            tno=list[head];
            tno.x= list[head].x+ dx[i];  tno.y= list[head].y+ dy[i];
            if( tno.x>=1 &&tno.x<=3&& tno.y>=1&&tno.y<=3)
            {
                 tt= tno.a[tno.x][tno.y];
                 tno.a[tno.x][tno.y]= tno.a[list[head].x][list[head].y];
                 tno.a[list[head].x][list[head].y]=tt;
                 tno.dep= list[head].dep+1;
                 if( check( tno)==false )
                 {
                     tail++;
                     list[tail]=tno;
                     if( tf( tno, list[0] )==true )
                     {
                        printf("%d\n",list[tail].dep);
                        bk=true;break;
                     }
                 }
            }
        }
        if( bk==true) break;

        head++;
     }
    return 0;
}