【双向BFS】黑白棋游戏题解

#include<bits/stdc++.h>
using namespace std;
int start[4][4],target[4][4];
void input(int a[4][4]){
    for(int i=0;i<4;i++){
        for(int j=0;j<4;j++){
            char c;
            cin>>c;
            a[i][j]=c-'0';
        }
    }
}
string s_to_string(int s[4][4]){
    string res;
    for(int i=0;i<4;i++)
        for(int j=0;j<4;j++)
                res+=s[i][j]+'0';
    return res;
}
vector<string> s_swap(int cur[4][4]){
    vector<string> res;
    for(int i=0;i<4;i++){
        for(int j=0;j<3;j++){
            swap(cur[i][j],cur[i][j+1]);
            res.push_back(s_to_string(cur));
            swap(cur[i][j],cur[i][j+1]);
        }
    }
    for(int j=0;j<4;j++){
        for(int i=0;i<3;i++){
            swap(cur[i][j],cur[i+1][j]);
            res.push_back(s_to_string(cur));
            swap(cur[i][j],cur[i+1][j]);
        }
    }
    return res;
} 
int main(){
    input(start); input(target);
    map<string,int> diss,dist;
    queue<string> qs,qt;
    string ss=s_to_string(start),st=s_to_string(target);
    if(ss==st){
        cout<<0;
        return 0;
    }
    qs.push(ss); diss[ss]=0;
    qt.push(st); dist[st]=0;
    while(!qs.empty()&&!qt.empty()){
        if(qs.size()<=qt.size()){
            string f=qs.front();
            qs.pop();
            int nxt[4][4];
            for(int i=0;i<f.size();i++)
                nxt[i/4][i%4]=f[i]-'0';
            vector<string> next=s_swap(nxt);
            for(int i=0;i<next.size();i++){
                if(!diss.count(next[i])){
                    diss[next[i]]=diss[f]+1;
                    qs.push(next[i]);
                }
                if(dist.count(next[i])){
                    cout<<diss[next[i]]+dist[next[i]];
                    return 0;
                }
            }
        }
        else{
            string f=qt.front();
            qt.pop();
            int nxt[4][4];
            for(int i=0;i<f.size();i++)
                nxt[i/4][i%4]=f[i]-'0';
            vector<string> next=s_swap(nxt);
            for(int i=0;i<next.size();i++){
                if(!dist.count(next[i])){
                    dist[next[i]]=dist[f]+1;
                    qt.push(next[i]);
                }
                if(diss.count(next[i])){
                    cout<<diss[next[i]]+dist[next[i]];
                    return 0;
                }
            }
        }
    }
}