将图的所有状态都存下来,一步一步bfs遍历,但是需要去重,由于重载运算符过于复杂,因此考虑用双哈希去重
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int mod1=1e9+7; const int mod2=1e9+9; int base=11; struct X{ int x,y; int x1,y1; }; struct node{ X s[11]; int cnt; int g[10][10]; }tmp; map<ll,int> m1; int g[10][10]; int mx; bool check(node x){ int a1=x.s[1].x; int b1=x.s[1].y; int a2=x.s[1].x1; int b2=x.s[1].y1; if(a2==3&&b2==6) return true; return false; } ll get(node x){ ll t1=0; ll t2=0; int i,j; for(i=1;i<=6;i++){ for(j=1;j<=6;j++){ t1=(t1*base%mod1+x.g[i][j])%mod1; t2=(t2*base%mod2+x.g[i][j])%mod2; } } return t1*base+t2; } int bfs(){ int i,j; queue<node> q; tmp.cnt=0; ll hs=get(tmp); m1[hs]++; q.push(tmp); int ans=-1; while(q.size()){ auto x=q.front(); q.pop(); if(check(x)){ ans=x.cnt; break; } for(int sign=1;sign<=mx;sign++){ int a1=x.s[sign].x; int b1=x.s[sign].y; int a2=x.s[sign].x1; int b2=x.s[sign].y1; if(b1==b2){ if(a1-1>=1&&x.g[a1-1][b1]==0){ node ean=x; ean.s[sign].x=a1-1; ean.s[sign].y=b1; ean.s[sign].x1=a2-1; ean.s[sign].y1=b2; ean.g[a1-1][b1]=sign; ean.g[a2][b2]=0; ll hs=get(ean); if(!m1[hs]){ ean.cnt+=1; m1[hs]++; q.push(ean); } } if(a2+1<=6&&x.g[a2+1][b2]==0){ node ean=x; ean.s[sign].x=a1+1; ean.s[sign].y=b1; ean.s[sign].x1=a2+1; ean.s[sign].y1=b2; ean.g[a2+1][b2]=sign; ean.g[a1][b1]=0; ll hs=get(ean); if(!m1[hs]){ ean.cnt+=1; m1[hs]++; q.push(ean); } } } else if(a1==a2){ if(b1-1>=1&&x.g[a1][b1-1]==0){ node ean=x; ean.s[sign].x=a1; ean.s[sign].y=b1-1; ean.s[sign].x1=a2; ean.s[sign].y1=b2-1; ean.g[a1][b1-1]=sign; ean.g[a2][b2]=0; ll hs=get(ean); if(!m1[hs]){ ean.cnt+=1; m1[hs]++; q.push(ean); } } if(b2+1<=6&&x.g[a2][b2+1]==0){ node ean=x; ean.s[sign].x=a1; ean.s[sign].y=b1+1; ean.s[sign].x1=a2; ean.s[sign].y1=b2+1; ean.g[a2][b2+1]=sign; ean.g[a1][b1]=0; ll hs=get(ean); if(!m1[hs]){ ean.cnt+=1; m1[hs]++; q.push(ean); } } } } } if(ans!=-1&&ans<9) return ans+2; return -1; } int main(){ int i,j; for(i=1;i<=6;i++){ for(j=1;j<=6;j++){ cin>>g[i][j]; mx=max(mx,g[i][j]); } } for(i=1;i<=6;i++){ for(j=1;j<=6;j++){ tmp.g[i][j]=g[i][j]; } } for(int sign=1;sign<=mx;sign++){ int flag=0; for(i=1;i<=6;i++){ for(j=1;j<=6;j++){ if(g[i][j]==sign){ if(g[i][j+2]==sign){ tmp.s[sign]={i,j,i,j+2}; flag=1; break; } if(g[i][j+1]==sign){ tmp.s[sign]={i,j,i,j+1}; flag=1; break; } if(g[i+2][j]==sign){ tmp.s[sign]={i,j,i+2,j}; flag=1; break; } if(g[i+1][j]==sign){ tmp.s[sign]={i,j,i+1,j}; flag=1; break; } } } if(flag) break; } } cout<<bfs()<<endl; }