UVA 1601 The Morning after Halloween

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题意：

给出一个最大为16×16的迷宫图和至多3个ghost的起始位置和目标位置，求最少经过几轮移动可以使三个ghost都到达目标位置。每轮移动中，每个ghost可以走一步，也可以原地不动，需要注意的是任意两个ghost不能在相同的位置，也不能出现任意两个ghost对穿。每个迷宫图'#'表示墙，' '表示空地，小写字母表示ghost的起始位置，大写字母表示对应ghost的目标位置。保证任意2×2的空间内都有一个'#'。

分析：

迷宫图给转换成了图，用邻接表保存起来，这样搜索的时候只走可以走的点。根据任意2×2都有'#'这个细节，可以粗略的估计出整个迷宫中可以走的空地不超过200个，3个ghost的话建一个三维数组vis。num数组记录当前是第几个非#地。g[num][0]记录第num个非#地的上下左右有几个非#地。接下来g[num][1]-g[num][num]代表非#地的序号。

代码：

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <queue>
using namespace std;
char map[20][20];
int num[20][20];
int g[200][200];
int vis[200][200][200];
int cnt;
int w,h,n;
int que[10000000][4];
int goal[4];
void bfs()
{
memset(vis,0,sizeof(vis));
int fro=0,rear=1;
vis[que[0][1]][que[0][2]][que[0][3]]=true;
while(fro<rear)
{
int i,j,k,t1,t2,t3;
int &step=que[fro][0],&a=que[fro][1],&b=que[fro][2],&c=que[fro][3];
if(a == goal[1] && b == goal[2] && c == goal[3]) { goal[0] = step; return; }
for(i=0;i<=g[a][0];i++)
{
t1=(i==0?a:g[a][i]);
for(j=0;j<=g[b][0];j++)
{
t2=(j==0?b:g[b][j]);
for(k=0;k<=g[c][0];k++)
{
t3=(k==0?c:g[c][k]);
if((t1&&t2&&t1==t2)||(t1&&t3&&t1==t3)||(t2&&t3&&t2==t3))
continue;
if(t1&&t2&&t1==b&&t2==a)
continue;
if(t1&&t3&&t1==c&&t3==a)
continue;
if(t3&&t2&&t3==b&&t2==c)
continue;
if(!vis[t1][t2][t3])
{
vis[t1][t2][t3]=1;
que[rear][0]=step+1,que[rear][1]=t1,que[rear][2]=t2,que[rear][3]=t3;
++rear;
}
}
}
}
++fro;
}
}
int main()
{
while(scanf("%d%d%d",&w,&h,&n)&&w&&h&&n)
{
int i,j,k;
cnt=0;
gets(map[0]);
for(i=0;i<h;i++)
gets(map[i]);
for(i=0;i<h;i++)
for(j=0;j<w;j++)
if(map[i][j]!='#')
num[i][j]=++cnt;
else
num[i][j]=0;

memset(g,0,sizeof(g));
for(i=0;i<h;i++)
{
for(j=0;j<w;j++)
{
if(num[i][j])
{
int &pos=num[i][j];
if(num[i+1][j])
g[pos][++g[pos][0]]=num[i+1][j];
if(num[i-1][j])
g[pos][++g[pos][0]]=num[i-1][j];
if(num[i][j+1])
g[pos][++g[pos][0]]=num[i][j+1];
if(num[i][j-1])
g[pos][++g[pos][0]]=num[i][j-1];
}
}
}
que[0][0]=que[0][1]=que[0][2]=que[0][3]=0;
goal[0]=goal[1]=goal[2]=goal[3]=0;
for(i=0;i<h;++i)
{
for(j=0;j<w;++j)
{
if(map[i][j] == 'a')
que[0][1] = num[i][j];
if(map[i][j] == 'b')
que[0][2] = num[i][j];
if(map[i][j] == 'c')
que[0][3] = num[i][j];
}
}
for(i=0;i<h;++i)
{
for(j=0;j<w;++j)
{
if(map[i][j] == 'A')
goal[1] = num[i][j];
if(map[i][j] == 'B')
goal[2] = num[i][j];
if(map[i][j] == 'C')
goal[3] = num[i][j];
}
}
bfs();
printf("%d\n",goal[0]);
}
}