太感人了，错了一天看了一天，终于AC了！ 仿佛人生度过了几个轮回呜呜呜
这题，看题解都是双向BFS,因为双向比单向快了好多 双向，说白就是一键双开，让你在开前面的时候顺便开后面，用两个队列也行，一个队列更好写，因为你得开完两个队列前面一层再开后面一层，你只要用一个 flag标记一下前后即可 1. 然后正向与反向有什么区别呢，正向遇到反向的最小，才是最小，而反向的最小遇到正向，此时不一定是最小 例如题目的顺序是 dlru 那么你两边都是从dlru那么走， 假设你的后面走了dl 忽然发现前面有一个u刚好可以，那你就直接 udl输出 而实际上 后面来的 ul 哭了 ，它遇到了 d 是 dul 为啥子它比较小反而不行，那怎么办呢，只能后面的时候只储存就好啦，反正正向迟早可以找到自己的！省的闹麻烦勒 还有一件事，后面走的，，如果 你先来一个 ud ，后面 来了一个 du ,你和它走到了相同的位置， 不就很尴尬？ 所以你必须要比较一下谁大谁占坑！顺便别忘了把 du 也队列放进去跑哦 2. 接下来比较不会考虑的是存储路经 用string 感觉太大，所以采用4进制的long long 来存储，但又有一个问题，如果它一直走d，不就一直0？所以为了防止漏0，俺先给它赋值为1 正向直接就 （4进制表示） 1->10->103->1032 反向为了防止比较大小的时候出错，所以把它采用正向储存，用了一个path数组来储存4进制进位，其就为 1 -> 13 -> 123 -> 1023 这个样子 在方向的时候需注意：反向走dlru的时候 下则要走上！左则要走右！为了走dlru,所以写了 3-i 3. map<string, long long> 会炸TLE map<long long , long long> 不会 4. 第一步要注意不用乱把不该放的放进去 不然你可能会 MLE 代码如下
#include <iostream> #include <cstdio> #include <algorithm> #include <queue> #include <string> #include <cstring> #include <map> using namespace std; string be,en; //储存开始序列和结束序列 long long s1,s2;//存正向和反向要输出的 char ss[1000];//用于输出 int dis[4][2]= { {1,0},{0,-1},{0,1},{-1,0} }; //dlru正 反ulrd char c[]="dlru"; long long path[100];//存储4进制 long long pu(string s)//将序列化为数字存储状态 { long long sum = 0; int n = s.size(); for (int i = 0; i < n; i++) { sum = sum*10+((s[i] == 'X')?0:s[i]-'0'); } return sum; } struct stu{ long long wei;//储存已经走的路劲 int flag; //正反 string S; //目前队列 int bu; //已走步数 }; map <long long , long long> C,C1; // 状态存储 顺便路劲储存 void BFS() { C.clear(); C1.clear(); //初始化 if(be == en) return ; //一样的情况 stu Be,Nex,En; long long s = pu(be); C[s] = 1; Be.wei = 1; Be.flag = 0; Be.S = be; s = pu(en); C1[s] = 1; En.wei = 1; En.flag = 1; En.S = en; Be.bu = 0; En.bu = 0; queue <stu> q; q.push(Be); q.push(En); while( !q.empty() ){ Be = q.front(); q.pop(); int W = 0; for (int i = 0; i < 9; i++) if(Be.S[i] == 'X') { //找到0 的位置 W = i; break; } int x = W/3, y = W%3; for (int i = 0; i < 4; i++){ Nex = Be; Nex.bu++; // 先加一步 int newx,newy; if(!Be.flag) //为了走dlru { newx = x + dis[i][0],newy = y + dis[i][1]; } else{ newx = x + dis[(3-i)][0],newy = y + dis[(3-i)][1]; //3-i } int newW = newx*3 + newy; if(newx >= 0 && newx < 3 && newy >= 0 && newy < 3 ){ swap(Nex.S[W],Nex.S[newW]); long long s = pu(Nex.S); if(!Be.flag && !C.count(s)){ Nex.wei = Nex.wei*4 + i; //推的 C[s] = Nex.wei; if(C1.count(s)){ s1 = C[s]; s2 = C1[s]; return; } q.push(Nex); } else if( Be.flag ){ Nex.wei = Nex.wei-path[Be.bu]*1 + i*path[Be.bu] + 1*path[Nex.bu];//推的 if(!C1.count( s )){ C1[ s ] = Nex.wei; q.push(Nex); } else{ if( C1[s] > Nex.wei ) { C1[s] = Nex.wei; q.push(Nex); } } /*if(C.count((Nex.S))){ s1 = C[Nex.S]; s2 = C1[Nex.S]; return; }*///没有权力，只能等人拯救 } } } } } int main() { int n; int k = 1; for (int i = 0; i < 30;i++) { path[i] = k; k*=4; }//将四进制阶数求出 scanf("%d",&n); for (int i = 0; i < n; i++) { memset(ss,0,sizeof(ss)); int mm = 0; cin >> be >> en; s1 = 1; s2 = 1; BFS(); //十进制转四进制 while(s1!=1 && s1>0){ int k = s1%4; ss[mm++] = c[k]; s1/=4; } for (int j = 0; j < mm/2; j++){ char t = ss[j]; ss[j] = ss[mm-j-1]; ss[mm-j-1] = t; } int zz = mm; while(s2!=1 && s2>0){ int k = s2%4; ss[mm++] = c[k]; s2/=4; } printf("Case %d: %d\n",i+1,mm); for (int i = 0; i < zz; i++){ printf("%c",ss[i]); } for (int i = mm-1; i >= zz; i--){ printf("%c",ss[i]); } printf("\n"); } }