题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3567
解题思路:
根据X的位置将初始状态分为9种:first[9][10]=
{"X12345678", "1X2345678", ......, "12345678X"}。对于每一种初始状态,根据X的位置找到对应的 first[][]。比如说,对于146X25378到2478356X1的转换,146X25378对应的就是123X45678,那么此时2代表的其实就是4,3代表的就是6,4代表的是2,6代表的是3,那么2478356X1对应的就是4278653X1,我们只要求123X45678到4278653X1的转换就可以了。
这样一来这道题其实就跟HDU1042差不多了。我们还是用state这个结构体来表示每一种状态,用康托展开来为每一种状态找到一个对应的数。先以九个first[]为起点做9次BFS,记录下从每个firtst[]能到达的各个状态,然后正式询问的时候直接利用预处理好的信息来返回答案就好了。
具体的几个细节看代码注释吧。
AC代码:
1 #include <cstdio> 2 #include <cstring> 3 #include <map> 4 using namespace std; 5 const int maxn = 5e5; 6 int cx[4] = { 1,0,0,-1 }, cy[4] = { 0,-1,1,0 }; 7 char go[6] = "dlru"; 8 9 struct state { 10 int from; //记录上一个状态,方便后期方向读取and 11 int pos; //记录X的位置 12 char num[10]; 13 char dos; //记录从上一步走到这一步要进行的操作 14 }; 15 state node[9][maxn]; 16 int vis[9][maxn]; //记录对应的状态在node[][]数组中的位置 17 char first[9][10] = { "X12345678","1X2345678","12X345678","123X45678","1234X5678","12345X678","123456X78","1234567X8","12345678X" }; 18 map<char, char> lists; //记录在此次询问中,1~8各个数字对应的数字 19 //康托展开 20 int factor[] = { 1,1,2,6,24,120,720,5040,40320,362880 }; 21 int cantor(char x[]) { 22 int sum = 0, s; 23 for (int i = 0; i<9; i++) { 24 s = 0; 25 for (int j = i + 1; j<9; j++) { 26 if (x[j]<x[i]) s++; 27 } 28 sum += s*factor[9 - i - 1]; 29 } 30 return sum; 31 } 32 void init(char now[10], int ind) { 33 node[ind][0].from = -1, node[ind][0].pos = ind; 34 for (int i = 0; i<9; i++) node[ind][0].num[i] = now[i]; 35 node[ind][0].num[9] = '