这是我写的一道题： https://www.luogu.com.cn/training/593464

本来我的初衷是用双向广搜写的，但是由于本人实在是太菜了，代码写出来，一直过不去。

代码：

#include<bits/stdc++.h>
using namespace std;
int t,n,c,sx1,sy1,sx2,sy2,fx1,fy1,fx2,fy2;
string s;
struct quiz{
    string s;
    int x1,y1,x2,y2,step;
};
int dx[5] = {1,-1,0,0};
int dy[5] = {0,0,1,-1};
int main(){
    //freopen("test.in","r",stdin);
    //freopen("test.out","w",stdout);
    cin >> t;
     map<string,int> mp;
     set<string> am;
     queue<quiz> q;
    while(t--){
        int flag = 0;
        cin >> n;
        s = "";
        for(int i = 1;i <= n;i++){
            for(int j = 1;j <= n;j++){
                cin >> c;
                if(c == 0){
                    if(sx1 == 0) sx1 = i,sy1 = j;
                    else sx2 = i,sy2 = j;
                }
                s += (char)(c + '0');
            }
        }
        mp.insert({s,0});
        q.push({s,sx1,sy1,sx2,sy2,0});
        s = "";
        for(int i = 1;i <= n;i++){
            for(int j = 1;j <= n;j++){
                cin >> c;
                if(c == 0){
                    if(fx1 == 0) fx1 = i,fy1 = j;
                    else fx2 = i,fy2 = j;
                }
                s += (char)(c + '0');
            }
        }
        while(!q.empty()){
            struct quiz tmp = q.front();q.pop();
            if(tmp.step == 6) continue;
            if(tmp.s == s){
                cout<<tmp.step<<endl;
                flag = 1;break;
            }
            for(int i = 0;i < 4;i++){
                struct quiz tmp2 = tmp;
                if(tmp2.x1 + dx[i] > 0 && tmp2.x1 + dx[i] <= n && tmp2.y1 + dy[i] > 0 && tmp2.y1 + dy[i] <= n){
                    if(tmp2.x1 + dx[i] != tmp2.x2 || tmp2.y1 + dy[i] != tmp2.y2){
                        swap(tmp2.s[(tmp2.x1 + dx[i] - 1) * n + tmp2.y1 + dy[i] - 1],tmp2.s[(tmp2.x1 - 1) * n + tmp.y1 - 1]);
                        if(mp.find(tmp2.s) == mp.end()){
                            mp.insert({tmp2.s,tmp2.step + 1});
                            q.push({tmp2.s,tmp2.x1 + dx[i],tmp2.y1 + dy[i],tmp2.x2,tmp2.y2,tmp2.step + 1});
                        }
                    }  
                }
            }
            for(int i = 0;i < 4;i++){
                struct quiz tmp2 = tmp;
                if(tmp2.x2 + dx[i] > 0 && tmp2.x2 + dx[i] <= n && tmp2.y2 + dy[i] > 0 && tmp2.y2 + dy[i] <= n){
                    if(tmp2.x2 + dx[i] != tmp2.x1 || tmp2.y2 + dy[i] != tmp2.y1){
                        swap(tmp2.s[(tmp2.x2 + dx[i] - 1) * n + tmp2.y2 + dy[i] - 1],tmp2.s[(tmp2.x2 - 1) * n + tmp.y2 - 1]);
                        if(mp.find(tmp2.s) == mp.end()){
                            mp.insert({tmp2.s,tmp2.step + 1});
                            q.push({tmp2.s,tmp2.x1,tmp2.y1,tmp2.x2 + dx[i],tmp2.y2 + dy[i],tmp2.step + 1});
                        }
                    }  
                }
            }
        }
        if(flag == 1) continue;
        q.push({s,fx1,fy1,fx2,fy2,0});
        while(!q.empty()){
            struct quiz tmp = q.front();q.pop();
            if(tmp.step == 6) continue;
            for(int i = 0;i < 4;i++){
                struct quiz tmp2 = tmp;
                if(tmp2.x1 + dx[i] > 0 && tmp2.x1 + dx[i] <= n && tmp2.y1 + dy[i] > 0 && tmp2.y1 + dy[i] <= n){
                    if(tmp2.x1 + dx[i] != tmp2.x2 || tmp2.y1 + dy[i] != tmp2.y2){
                        swap(tmp2.s[(tmp2.x1 + dx[i] - 1) * n + tmp2.y1 + dy[i] - 1],tmp2.s[(tmp2.x1 - 1) * n + tmp.y1 - 1]);
                        if(am.find(tmp2.s) == am.end()){
                            am.insert(tmp2.s);
                            cout<<tmp2.s<<endl;
                            if(mp.find(tmp2.s) != mp.end()){
                                cout<<mp.find(tmp2.s) -> second + tmp2.step + 1<<'\n';
                                flag = 1;break;
                            }
                            q.push({tmp2.s,tmp2.x1,tmp2.y1,tmp2.x2 + dx[i],tmp2.y2 + dy[i],tmp2.step + 1});
                        }
                    }  
                }
            } 
            if(flag == 1) break;
            for(int i = 0;i < 4;i++){
                struct quiz tmp2 = tmp;
                if(tmp2.x2 + dx[i] > 0 && tmp2.x2 + dx[i] <= n && tmp2.y2 + dy[i] > 0 && tmp2.y2 + dy[i] <= n){
                    if(tmp2.x2 + dx[i] != tmp2.x1 || tmp2.y2 + dy[i] != tmp2.y1){
                        swap(tmp2.s[(tmp2.x2 + dx[i] - 1) * n + tmp2.y2 + dy[i] - 1],tmp2.s[(tmp2.x2 - 1) * n + tmp.y2 - 1]);
                        if(am.find(tmp2.s) == am.end()){
                            am.insert(tmp2.s);
                                                       if(mp.find(tmp2.s) != mp.end()){
                                cout<<mp.find(tmp2.s) -> second + tmp2.step + 1<<'\n';
                                flag = 1;break;
                            }
                            q.push({tmp2.s,tmp2.x1,tmp2.y1,tmp2.x2 + dx[i],tmp2.y2 + dy[i],tmp2.step + 1});
                        }
                    }  
                }
            }
            if(flag == 1) break;
        }
        if(flag == 0) cout<<"You have been deceived!"<<'\n';
        mp.clear();
        am.clear();
        while(!q.empty()){q.pop();}
    }
    return 0;
}

输入：

2
3
1 0 0
4 3 2
7 6 5
1 2 3
4 5 6
7 0 0
3
1 2 3
4 0 0
7 6 5
1 2 3
4 5 6
7 0 0

正常输出：8 4
错误输出：8 8