problem
solution
codes
#include<iostream> #include<algorithm> #include<queue> #include<string> #include<map> using namespace std; const int dx[] = {0,0,-1,1}; const int dy[] = {1,-1,0,0}; string goal = "123804765", s; map<string,int>ma; int main(){ cin>>s; queue<string>q; q.push(s); while(!q.empty()){ string t = q.front(); q.pop(); if(t == goal)break; int z; for(z = 0; z < 9; z++) if(t[z]=='0')break; int x=z/3, y=z%3; for(int i = 0; i < 4; i++){ int nx=x+dx[i], ny=y+dy[i], nz=nx*3+ny; if(nx<0||nx>=3||ny<0||ny>=3)continue; string tt = t; swap(tt[z],tt[nz]); if(!ma.count(tt)){ q.push(tt); ma[tt] = ma[t]+1; } } } cout<<ma[goal]<<"\n"; return 0; }