BFS

时间复杂度

C++ 代码

#include<iostream>
#include<queue>
using namespace std;
const int N=16;
int start, ed, st[1<<N];
char c[4][4];
int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};

void show(int x){
    for(int i=15; i>=0; i--){
        int t = (x>>i)&1;
        cout<<t;
        if(i%4==0) cout<<endl;    
    }
    cout<<endl;
}
int bfs(){
    queue<int> q;
    q.push(start);
    st[start] = 0;
    while(q.size()){
        int p=q.front(); q.pop();
        // show(p);
        if(p==ed){
            return st[p];
        }
        for(int i=15; i>=0; i--){
            int x=(15-i)/4, y=(15-i)%4;
            //枚举这个点的可能的四个方向
            for(int k=0; k<4; k++){
                int nx=x+dir[k][0], ny=y+dir[k][1];
                if(nx<0||nx>=4||ny<0||ny>=4) continue;
                int ni=(15-(nx*4+ny));
                if((p&(1<<i)) == (p&(1<<ni))) continue; //当需要交换的两个位置的元素不相同的时候才进行交换
                int state=(p^(1<<i)^(1<<ni));
                if(st[state]) continue;
                st[state] = st[p]+1;
                q.push(state);
            }
        }
    }
    return -1;
}
int main(){
    char op;
    for(int i=0; i<4; i++) cin>>c[i];
    for(int i=0; i<4; i++)
        for(int j=0; j<4; j++){
            start <<= 1;
            start += (c[i][j]=='1');
        }

    for(int i=0; i<4; i++) cin>>c[i];
    for(int i=0; i<4; i++)
        for(int j=0; j<4; j++){
            ed <<= 1;
            ed += (c[i][j]=='1');
        }
    cout<<bfs();
}