调试了一段时间了，起点没有标记搜索过。大二的集训题目，现在才做。1Y。题目有点水。以前每次想做都是做不下去。今天K了
直接广搜就行了。将每个状态都标记，大概就10000个状态，以前总是不会分析，以为一定爆各种。。。
#include#include using namespace std;int sn , en;char sts[6] , eds[6];int vis[10000],stp[10000];void init(){ memset(vis,0,sizeof(vis)); memset(stp,0,sizeof(stp));}int ex[4] , rl[10] , num[4];int Ex[4][4] , Rl[10][4];int tonum(int a,int b,int c,int d){ return a*1000+b*100+c*10+d;}void exch(int tmp){ num[0] = tmp/1000; num[1] = tmp%1000/100; num[2] = tmp%100/10; num[3] = tmp%10; int i=0; for(int j=0;j<3;j++){ for(int ti=0;ti<4;ti++) Ex[j][ti] = num[ti]; int t = Ex[j][i]; Ex[j][i] = Ex[j][i+1]; Ex[j][i+1] = t; //Swap(Ex[j][i],Ex[j][i+1]); ex[j] = tonum(Ex[j][0],Ex[j][1],Ex[j][2],Ex[j][3]); i++; }}inline int cor(int a) { if(a == 10) return 1; if(a == 0) return 9; return a;}void roll(int tmp){ num[0] = tmp/1000; num[1] = tmp%1000/100; num[2] = tmp%100/10; num[3] = tmp%10; for(int i=0;i<8;i++){ for(int k=0;k<4;k++) Rl[i][k] = num[k]; } for(int i=0;i<4;i++){ Rl[i*2][i] = cor(Rl[i*2][i] - 1); Rl[i*2+1][i] = cor(Rl[i*2+1][i] + 1); } for(int i=0;i<8;i++){ rl[i] = tonum(Rl[i][0],Rl[i][1],Rl[i][2],Rl[i][3]); //printf("%d ",rl[i]); }}int fa[10000];int bfs(){ init(); queue q; q.push(sn); stp[sn] = 0; vis[sn] = 1; while(!q.empty()){ int tn = q.front();q.pop(); if(tn == en) return stp[tn]; exch(tn); for(int i=0;i<3;i++){ if(vis[ex[i]] == 0){ vis[ex[i]] = 1; q.push(ex[i]); stp[ex[i]] = stp[tn]+1; fa[ex[i]] = tn; } } roll(tn); for(int i=0;i<8;i++){ if(vis[rl[i]] == 0){ vis[rl[i]] = 1; q.push(rl[i]); stp[rl[i]] = stp[tn]+1; fa[rl[i]] = tn; } } } return 0;}int main(){ int T; scanf("%d",&T); while(T--){ scanf("%s %s",sts,eds); sn = atoi(sts); en = atoi(eds); printf("%d\n" , bfs()); } return 0;}
可以递归找到变化路径。挺简单的。不多说了。