题解 P7724 【远古档案馆（Ancient Archive）】

posted on 2021-07-14 19:19:57 | under 题解 | source

首先我们先算一下网格最多可能有多少种状态，很显然是 \(5^4=625\)，完全可以暴力搜索。

那怎么实现呢？可以使用 bfs，以初始状态开始，每次找空格子，将空格子四周的数字移过来，完成状态的扩展。

但这样子极有可能重复搜索同一种状态，我们需要去重。经测试使用 std::map 会 MLE/TLE，所以我们使用 hash。观察到题面有一句话：

且它们就是前 \(\bold{k}\) 个不同的正整数。

换句话说，数字全都是一位数，可以把四个数字压缩成一个四位数，这样就不会 MLE/TLE 了。

这里给出我的代码实现：

#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;
const int dx[]={0,-1,0,0,1},
          dy[]={0,0,-1,1,0};
int n=2;
struct node{
    int a[3][3];
    friend istream& operator>>(istream &fin,node &e){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                fin>>e.a[i][j];
            }
        }
        return fin;
    }
    operator int(){
        return a[1][1]*1
              +a[1][2]*10
              +a[2][1]*100
              +a[2][2]*1000;
    }
};
queue<node> q;
bool vis[10010];
node begin,end;
bool bfs(){
    vis[begin]=1;
    q.push(begin);
    while(!q.empty()){
        node now=q.front();q.pop();
        if(now==end) return 1;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(now.a[i][j]==0){
                    for(int k=1;k<=4;k++){
                        int x=i+dx[k],y=j+dy[k];
                        if(1<=x&&x<=n&&1<=y&&y<=n&&now.a[x][y]!=0){
                            node pus=now;
                            swap(pus.a[i][j],pus.a[x][y]);
                            if(!vis[pus]){
                                vis[pus]=1;
                                q.push(pus);
                            }
                        }
                    }
                }
            }
        }
    }
    return 0;
}
int main(){
    cin>>begin>>end;
    cout<<(bfs()?"Yes":"No")<<endl;
    return 0;
}