去年区域赛的题目，早就看过题目了，又是过了好久了。。。
这题状态转移，一看就知道应该是 线性的那种，不过细节真的不好处理，一直没想出怎么搞，期间也看过题解，好像没太看懂。。。
dp[i][j]表示前i位相同，i之后两位为j的最小转动次数。
例如dp[i][x*10+y] i+3位 为z（初始数字)，x y z 转化为 ax ay az，ax肯定是第二个串的第i位，后两位随便就可以。
只要 预处理 xyz 转化为axayaz的情况，就行了。dp[0]初始化，100位直接Floyd，其他的1000位的预处理，用spfa搞的。
预处理写的很长。。
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 using namespace std; 9 #define INF 10000000 10 char s1[1200],s2[1200]; 11 int dp[1010][110]; 12 int mp[1010][1010]; 13 int dis[1010]; 14 int in[1010]; 15 int p[101][101]; 16 int n1[1010],n2[1010]; 17 int a[12] = { 1,0,0,1,0,1,-1,0,0,-1,0,-1}; 18 int b[12] = { 0,1,0,1,1,1,0,-1,0,-1,-1,-1}; 19 int c[12] = { 0,0,1,0,1,1,0,0,-1,0,-1,-1}; 20 void spfa(int key) 21 { 22 int x,y,z,i,ax,ay,az,u,v; 23 queue que; 24 for(i = 0;i < 1000;i ++) 25 { 26 dis[i] = INF; 27 in[i] = 0; 28 } 29 in[key] = 1; 30 dis[key] = 0; 31 que.push(key); 32 while(!que.empty()) 33 { 34 u = que.front(); 35 in[u] = 0; 36 que.pop(); 37 x = (u/100)%10; 38 y = (u/10)%10; 39 z = u%10; 40 for(i = 0;i < 12;i ++) 41 { 42 ax = (x+a[i]+10)%10; 43 ay = (y+b[i]+10)%10; 44 az = (z+c[i]+10)%10; 45 v = ax*100+ay*10+az; 46 if(dis[v] > dis[u] + 1) 47 { 48 if(!in[v]) 49 { 50 in[v] = 1; 51 que.push(v); 52 } 53 dis[v] = dis[u] + 1; 54 } 55 } 56 } 57 for(i = 0;i < 1000;i ++) 58 mp[key][i] = dis[i]; 59 return ; 60 } 61 int main() 62 { 63 int i,j,len,x,y,z,k,temp; 64 for(i = 0;i < 100;i ++) 65 { 66 for(j = 0;j < 100;j ++) 67 p[i][j] = INF; 68 p[i][i] = 0; 69 } 70 for(i = 0;i < 100;i ++) 71 { 72 x = (i/10)%10; 73 y = i%10; 74 p[x][(y+1)%10] = 1; 75 p[(y+1)%10][x] = 1; 76 p[(x+1)%10][y] = 1; 77 p[y][(x+1)%10] = 1; 78 p[(x+1)%10][(y+1)%10] = 1; 79 p[(y+1)%10][(x+1)%10] = 1; 80 } 81 for(i = 0;i < 100;i ++) 82 { 83 for(j = 0;j < 100;j ++) 84 { 85 for(k = 0;k < 100;k ++) 86 { 87 if(p[j][k] > p[j][i] + p[i][k]) 88 p[j][k] = p[j][i] + p[i][k]; 89 } 90 } 91 } 92 for(i = 0;i < 1000;i ++) 93 { 94 spfa(i); 95 } 96 while(scanf("%s%s",s1,s2)!=EOF) 97 { 98 len = strlen(s1); 99 for(i = 1;i <= len;i ++)100 {101 n1[i] = s1[i-1] - '0';102 n2[i] = s2[i-1] - '0';103 }104 for(i = 0;i <= len;i ++)105 {106 for(j = 0;j < 100;j ++)107 dp[i][j] = INF;108 }109 n1[len+1] = n2[len+1] = 0;110 n1[len+2] = n2[len+2] = 0;111 temp = n1[1] * 10 + n1[2];112 for(i = 0;i < 100;i ++)113 {114 dp[0][i] = p[temp][i];115 }116 for(i = 0;i < len;i ++)117 {118 z = n1[i+3];119 for(j = 0;j < 100;j ++)120 {121 x = (j/10)%10;122 y = j%10;123 for(k = 0;k < 100;k ++)124 {125 if(dp[i+1][k] > dp[i][j] + mp[j*10+z][n2[i+1]*100+k])126 dp[i+1][k] = dp[i][j] + mp[j*10+z][n2[i+1]*100+k];127 }128 }129 }130 printf("%d\n",dp[len][0]);131 }132 return 0;133 }