【1】题解：UVA1601 万圣节后的早晨 The Morning after Halloween【图论建模】【搜索】

· · 题解

首先我们看原题面文件，有重要的东西。

这句话的意思是：在一个 2\times 2 的格子中，至少有一个是障碍物。

那么我们的棋盘空格数就从预期的 wh 降到了 \frac{wh}{4}，这样我们动态开点的访问记录数组就从 w^3h^3 降到了 \frac{w^3h^3}{64}，不会爆空间。

这里提几个细节：

  1. 换行符可能是 \n 或 \r 所以读入时要判定，直到读入一个不为 \n 或 \r 的字符再存储。
  2. 鬼可以不动。
  3. 注意读题：两鬼不能交换。但是两个不存在的鬼可以相同位置也可以交换！
  4. 空间不要用太多。

其他没什么细节了。

#include<bits/stdc++.h>
using namespace std;
const int N=25,M=155;
int h,w,n,dot,sa,sb,sc,ea,eb,ec;
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
char a[N][N];
int idm[N][N];
bool vis[M][M][M];
vector<int>e[N*N];
queue<array<int,4>>q;
int main(){
    while(cin>>w>>h>>n){
        if(w==0&&h==0&&n==0)break;
        memset(vis,0,sizeof(vis));
        dot=sa=sb=sc=ea=eb=ec=0;
        e[0].push_back(0);
        for(int i=1;i<=h;i++){
            for(int j=1;j<=w;j++){
                a[i][j]=getchar();
                while(a[i][j]=='\r'||a[i][j]=='\n')a[i][j]=getchar(); // 读入处理
                if(a[i][j]!='#'){
                    idm[i][j]=++dot; // 动态开点
                    e[dot].clear();
                    e[dot].push_back(dot); // 鬼可以不动
                    if(a[i][j]=='a')sa=dot;
                    if(a[i][j]=='A')ea=dot;
                    if(a[i][j]=='b')sb=dot;
                    if(a[i][j]=='B')eb=dot;
                    if(a[i][j]=='c')sc=dot;
                    if(a[i][j]=='C')ec=dot;
                }else idm[i][j]=0; // 注意清空方式
            }
        }
        for(int i=1;i<=h;i++)
            for(int j=1;j<=w;j++)if(a[i][j]!='#')
                for(int d=0;d<4;d++){
                    int nx=i+dx[d],ny=j+dy[d];
                    if(nx<1||ny<1||nx>h||ny>w||!idm[nx][ny])continue;
                    e[idm[i][j]].push_back(idm[nx][ny]); // 建图
                }
        while(q.size())q.pop();
        q.push({sa,sb,sc,0});
        vis[sa][sb][sc]=1;
        while(q.size()){
            auto f=q.front();
            q.pop();
            if(f[0]==ea&&f[1]==eb&&f[2]==ec){
                cout<<f[3]<<"\n";
                break;
            }
            for(auto v0:e[f[0]])for(auto v1:e[f[1]])for(auto v2:e[f[2]]){
                if(v0&&v1&&((v0==f[1]&&v1==f[0])||(v0==v1)))continue;
                if(v0&&v2&&((v0==f[2]&&v2==f[0])||(v0==v2)))continue;
                if(v1&&v2&&((v1==f[2]&&v2==f[1])||(v1==v2)))continue;
                if(vis[v0][v1][v2])continue;
                vis[v0][v1][v2]=1;
                q.push({v0,v1,v2,f[3]+1});
            }
        }
    }
    return 0;
}