#include<cstdio> #include<cstring> #include<algorithm> #include<cstdlib> //#include<set> //#include<time.h> #include<math.h> //#include<assert.h> //#include<queue> //#include<iostream> using namespace std; typedef int Sta[11]; char s[11][9]; bool vis[370011];int dis[370011],kt[370011]; Sta que[370011];int head,tail; int inque(const Sta &nn) { if (ok(nn)) return d+1; memcpy(que[tail],nn,sizeof(Sta)); kt[tail]=kang(nn); dis[tail]=d+1; vis[kt[tail]]=1; tail++; return -1; } bool you1(Sta nn) { if (s[nn[1]][4]=='1' || s[nn[2]][4]=='1' || s[nn[3]][4]=='1') return 0; swap(nn[3],nn[2]); swap(nn[2],nn[1]); return 1; } bool you2(Sta nn) { if (s[nn[4]][4]=='1' || s[nn[5]][4]=='1' || s[nn[6]][4]=='1') return 0; swap(nn[6],nn[5]); swap(nn[5],nn[4]); return 1; } bool you3(Sta nn) { if (s[nn[7]][4]=='1' || s[nn[8]][4]=='1' || s[nn[9]][4]=='1') return 0; swap(nn[9],nn[8]); swap(nn[8],nn[7]); return 1; } bool zuo1(Sta nn) { if (s[nn[1]][4]=='1' || s[nn[2]][4]=='1' || s[nn[3]][4]=='1') return 0; swap(nn[1],nn[2]); swap(nn[2],nn[3]); return 1; } bool zuo2(Sta nn) { if (s[nn[4]][4]=='1' || s[nn[5]][4]=='1' || s[nn[6]][4]=='1') return 0; swap(nn[4],nn[5]); swap(nn[5],nn[6]); return 1; } bool zuo3(Sta nn) { if (s[nn[7]][4]=='1' || s[nn[8]][4]=='1' || s[nn[9]][4]=='1') return 0; swap(nn[7],nn[8]); swap(nn[8],nn[9]); return 1; } bool shang1(Sta nn) { if (s[nn[1]][4]=='1' || s[nn[4]][4]=='1' || s[nn[7]][4]=='1') return 0; swap(nn[1],nn[4]); swap(nn[4],nn[7]); return 1; } bool shang2(Sta nn) { if (s[nn[2]][4]=='1' || s[nn[5]][4]=='1' || s[nn[8][4]=='1') return 0; swap(nn[2],nn[5]); swap(nn[5],nn[8]); return 1; } bool shang3(Sta nn) { if (s[nn[3]][4]=='1' || s[nn[6]][4]=='1' || s[nn[9][4]=='1') return 0; swap(nn[3],nn[6]); swap(nn[6],nn[9]); return 1; } bool xia1(Sta nn) { if (s[nn[1]][4]=='1' || s[nn[4]][4]=='1' || s[nn[7]][4]=='1') return 0; swap(nn[7],nn[4]); swap(nn[4],nn[1]); return 1; } bool xia2(Sta nn) { if (s[nn[2]][4]=='1' || s[nn[5]][4]=='1' || s[nn[8][4]=='1') return 0; swap(nn[8],nn[5]); swap(nn[5],nn[2]); return 1; } bool xia3(Sta nn) { if (s[nn[3]][4]=='1' || s[nn[6]][4]=='1' || s[nn[9][4]=='1') return 0; swap(nn[9],nn[6]); swap(nn[6],nn[3]); return 1; } int kang(Sta nn) { int ans=0; for (int i=1;i<=9;i++) { int tmp=0; for (int j=i+1;j<=9;j++) if (a[j]<a[i]) tmp++; ans+=tmp*fac[9-i]; } return ans; } bool mark[11][4],col[4]; void dfs(int i,int j,int nowcol) { mark[i][j]=1; if (j==0 || j==1) { if (!mark[i][2] && getcol(s[nn[i]][2])==nowcol) dfs(i,2,nowcol); if (!mark[i][3] && getcol(s[nn[i]][3])==nowcol) dfs(i,3,nowcol); } if (j==2 || j==3) { if (!mark[i][1] && getcol(s[nn[i]][1])==nowcol) dfs(i,1,nowcol); if (!mark[i][0] && getcol(s[nn[i]][0])==nowcol) dfs(i,0,nowcol); } if (i!=3 && i!=6 && i!=9 && j==3) dfs(i+1,2,nowcol); if (i!=1 && i!=4 && i!=7 && j==2) dfs(i-1,3,nowcol); if (i!=1 && bool ok(Sta nn) { memset(mark,0,sizeof(mark)); memset(col,0,sizeof(col)); for (int i=1;i<=9;i++) for (int j=0;j<4;j++) if (!mark[i][j]) { int nowcol=getcol(s[nn[i]][j]); if (col[nowcol]) return 0; col[nowcol]=1; dfs(i,j,nowcol); } } int bfs() { head=0;tail=1;for (int i=1;i<=9;i++) que[0][i]=i; memset(vis,0,sizeof(vis)); kt[0]=kang(que[0]); dis[0]=0;vis[kt[0]]=1; if (ok(que[0])) return 0; while (head!=tail) { Sta now;memcpy(now,que[head],sizeof(Sta));const int d=dis[head];head++; Sta nn;int tmp; memcpy(nn,now,sizeof(Sta)); if (you1(nn)) if (!vis[kang(nn)]) if ((tmp=inque(nn))>=0) return tmp; memcpy(nn,now,sizeof(Sta)); if (you2(nn)) if (!vis[kang(nn)]) if ((tmp=inque(nn))>=0) return tmp; memcpy(nn,now,sizeof(Sta)); if (you3(nn)) if (!vis[kang(nn)]) if ((tmp=inque(nn))>=0) return tmp; memcpy(nn,now,sizeof(Sta)); if (zuo1(nn)) if (!vis[kang(nn)]) if ((tmp=inque(nn))>=0) return tmp; memcpy(nn,now,sizeof(Sta)); if (zuo2(nn)) if (!vis[kang(nn)]) if ((tmp=inque(nn))>=0) return tmp; memcpy(nn,now,sizeof(Sta)); if (zuo3(nn)) if (!vis[kang(nn)]) if ((tmp=inque(nn))>=0) return tmp; memcpy(nn,now,sizeof(Sta)); if (shang1(nn)) if (!vis[kang(nn)]) if ((tmp=inque(nn))>=0) return tmp; memcpy(nn,now,sizeof(Sta)); if (shang2(nn)) if (!vis[kang(nn)]) if ((tmp=inque(nn))>=0) return tmp; memcpy(nn,now,sizeof(Sta)); if (shang3(nn)) if (!vis[kang(nn)]) if ((tmp=inque(nn))>=0) return tmp; memcpy(nn,now,sizeof(Sta)); if (xia1(nn)) if (!vis[kang(nn)]) if ((tmp=inque(nn))>=0) return tmp; memcpy(nn,now,sizeof(Sta)); if (xia2(nn)) if (!vis[kang(nn)]) if ((tmp=inque(nn))>=0) return tmp; memcpy(nn,now,sizeof(Sta)); if (xia3(nn)) if (!vis[kang(nn)]) if ((tmp=inque(nn))>=0) return tmp; } } int main() { for (int i=1;i<=9;i++) scanf("%s",s[i]); fac[0]=1;for (int i=1;i<=9;i++) fac[i]=fac[i-1]*i; printf("%d ",bfs()); return 0; }