[Luogu2324]八数码难题

 1 #include<cstdio>
 2 #include<queue>
 3 #include<iostream>
 4 #include<cstring>
 5 using namespace std;
 6 inline int read(){
 7     int ans=0,f=1;char chr=getchar();
 8     while(!isdigit(chr)){if(chr=='-') f=-1;chr=getchar();}
 9     while(isdigit(chr)){ans=(ans<<3)+(ans<<1)+chr-48;chr=getchar();}
10     return ans*f;
11 }int a[4][4],x,y,ff;char chr;
12 const int S[4][4]={{0,0,0,0},{0,1,2,3},{0,8,0,4},{0,7,6,5}},dx[4]={0,1,-1,0},dy[4]={1,0,0,-1};
13 inline bool check(){
14     for(int i=1;i<=3;i++)
15         for(int j=1;j<=3;j++)
16             if(S[i][j]!=a[i][j]) return 0;
17     return 1;
18 }inline bool test(int x,int y){int ans=0;
19     for(int i=1;i<=3;i++)
20         for(int j=1;j<=3;j++)
21             if(S[i][j]!=a[i][j])
22                 if(++ans+x>y) return 0;
23     return 1;
24 }void dfs(int stp,int x,int y,int depth,int lst){
25     if(depth==stp){if(check()) ff=1;return;}
26     if(ff) return;
27     for(int i=0;i<4;i++){
28         int fx=x+dx[i],fy=y+dy[i];
29         if(fx<1||fy<1||fx>3||fy>3||lst+i==3) continue;
30         swap(a[x][y],a[fx][fy]);
31         if(test(stp,depth)&&!ff)    dfs(stp+1,fx,fy,depth,i);
32         swap(a[x][y],a[fx][fy]);
33     }
34 }
35 int main(){
36     for(int i=1;i<=3;i++)
37         for(int j=1;j<=3;j++){cin>>chr;if(chr=='0') x=i,y=j;a[i][j]=chr-48;}
38     if(check()){puts("0");return 0;}
39     int i=1;
40     while(i++){dfs(0,x,y,i,-1);if(ff){cout<<i;return 0;}}
41     return 0;
42 }