分析：
简单的bfs,但要注意因为输入cases很多，对每个初始状态都搜一遍会超时，其实可以从终止状态反向搜一遍，对搜到的每个状态打表存下即可。
代码：
//poj 3221
//sep9
#include <iostream>
#include <queue>
using namespace std;
int n;
int fac[]={1,1,2,6,24,120,720,5040,40320};
int vis[10000],g[10000];
int pos[8][8];
struct NODE
{int s[9];int loc;int status;
};int cantor(int s[])
{ int sum=0; for(int i=0;i<7;++i){ int cnt=0; for(int j=i+1;j<7;++j) if(s[i]>s[j]) ++cnt; sum+=cnt*fac[7-i-1]; } return sum;
} void bfs(NODE start)
{queue<NODE> open;NODE cur,nxt;memset(vis,0,sizeof(vis));memset(g,-1,sizeof(g));vis[start.status]=1;g[start.status]=0;open.push(start);while(!open.empty()){cur=open.front();open.pop();int cur_zero_pos=cur.loc;for(int i=1;i<=pos[cur_zero_pos][0];++i){int nxt_zero_pos=pos[cur_zero_pos][i];nxt=cur;swap(nxt.s[cur_zero_pos],nxt.s[nxt_zero_pos]);nxt.loc=nxt_zero_pos;nxt.status=cantor(nxt.s);if(vis[nxt.status]==0){open.push(nxt);g[nxt.status]=g[cur.status]+1;vis[nxt.status]=1;}}}
}int main()
{int cases;pos[0][0]=3,pos[0][1]=2,pos[0][2]=4,pos[0][3]=6;pos[1][0]=2,pos[1][1]=2,pos[1][2]=6;pos[2][0]=3,pos[2][1]=0,pos[2][2]=1,pos[2][3]=3;pos[3][0]=2,pos[3][1]=2,pos[3][2]=4;pos[4][0]=3,pos[4][1]=0,pos[4][2]=3,pos[4][3]=5;pos[5][0]=2,pos[5][1]=4,pos[5][2]=6;pos[6][0]=3,pos[6][1]=0,pos[6][2]=1,pos[6][3]=5;NODE ncur;for(int i=0;i<7;++i)ncur.s[i]=i;ncur.loc=0;ncur.status=cantor(ncur.s);bfs(ncur);scanf("%d",&cases);while(cases--){char ch[16];int s[16];scanf("%s",ch);for(int i=0;i<7;++i)s[i]=ch[i]-'0';int cantor_value=cantor(s);printf("%d\n",g[cantor_value]);} return 0;
}