【UVa】【BFS】1601 The Morning after Halloween_综合

UVa 1601 The Morning after Halloween

题目

◇题目传送门◆（由于UVa较慢，这里提供一份vjudge的链接）
◇题目传送门（vjudge）◆

题目大意

在一个 $W×HW\times H$ 的网格上有 $N(N≤3)N(N\le3)$ 个鬼，用小写字母表示。要求将所有鬼移动到对应的大写字母处。每步可以有多个鬼移动（均为上下左右四个方向之一），但每步结束之后任何两个鬼不能再同一个位置，也不能在一步之内交换位置。举个例子：
它有四种移动方式：
输入保证所有的空格连通，所有的障碍格也连通，且每个 $2×22\times2$ 的格子中有至少一个障碍格。输出最少的移动步数。

思路

P.s.如果有想看双向BFS版的读者请先看完思路后再点这里。

若我们以当前3个小写字母为状态，则问题就可转化为一个最短路问题，状态总数为 ${256}^3$ ，但每次转移时都需要用 $5^3$ 枚举每个小写字母的下一步的走法（因为可以不动）。

所以我们必须优化转移的代价。在题目条件中：“每个 $2×22\times2$ 的格子中有至少一个障碍格”暗示我们有很多格子都是障碍，并且大部分空格都和障碍相邻。所以，不是所有4个方向都能够移动。因此可以将空格提出来建一个图，而不是每次临时判断5种方案是否合法。

所以这道题就变为了图的最短路问题，使用BFS求解。

正解代码

#include<queue> #include<vector> #include<cstdio> #include<cstring> #include<algorithm> using namespace std;const int Maxw=20; const int Maxn=150; const int dir[][2]={
     {
     1,0},{
     -1,0},{
     0,1},{
     0,-1},{
     0,0}};int W,H,N,cnt; char Map[Maxw+5][Maxw+5]; int s[3],t[3]; vector<int> G[Maxn+5]; int id[Maxw+5][Maxw+5]; int X[Maxn+5],Y[Maxn+5];void Prepare() {
     memset(G,0,sizeof G);cnt=0;for(int i=0;i<H;i++)for(int j=0;j<W;j++)if(Map[i][j]!='#') {
     X[cnt]=i,Y[cnt]=j;id[i][j]=cnt;if('a'<=Map[i][j]&&Map[i][j]<='z')s[Map[i][j]-'a']=cnt;//找出起点if('A'<=Map[i][j]&&Map[i][j]<='Z')t[Map[i][j]-'A']=cnt;//找出终点cnt++;}//找出所以的空格，并为每个空格编号 }void BuildGraph() {
     for(int i=0;i<cnt;i++)for(int j=0;j<5;j++) {
     int tx=X[i]+dir[j][0],ty=Y[i]+dir[j][1];if(Map[tx][ty]!='#')//题目中已经保证最外一层是障碍，故不用判出界的情况。G[i].push_back(id[tx][ty]);}//为所有空格建图if(N<=2) {
     G[cnt].push_back(cnt);s[2]=t[2]=cnt;cnt++;}if(N<=1) {
     G[cnt].push_back(cnt);s[1]=t[1]=cnt;cnt++;}//若少了节点就补上一些虚拟节点，以简化代码 }//建图int d[Maxn+5][Maxn+5][Maxn+5];inline int getid(int a,int b,int c) {
     return (a<<16)|(b<<8)|c; }//将三个鬼的位置压成一个数 inline bool ok(int a1,int b1,int a2,int b2) {
     if(a2==b2||(a2==b1&&b2==a1))return false;return true; }//判断不合法的状态 int BFS() {
     queue<int> q;memset(d,-1,sizeof d);q.push(getid(s[0],s[1],s[2]));d[s[0]][s[1]][s[2]]=0;while(!q.empty()) {
     int u=q.front();q.pop();int a=(u>>16)&0xFF,b=(u>>8)&0xFF,c=u&0xFF;if(a==t[0]&&b==t[1]&&c==t[2])return d[a][b][c];//若找到了就返回for(int i=0;i<G[a].size();i++) {
     int ta=G[a][i];for(int j=0;j<G[b].size();j++) {
     int tb=G[b][j];if(!ok(a,b,ta,tb))continue;for(int k=0;k<G[c].size();k++) {
     int tc=G[c][k];if(!ok(a,c,ta,tc))continue;if(!ok(b,c,tb,tc))continue;if(d[ta][tb][tc]!=-1)continue;d[ta][tb][tc]=d[a][b][c]+1;q.push(getid(ta,tb,tc));}}}}return -1; }int main() {
     #ifdef LOACLfreopen("in.txt","r",stdin);freopen("out.txt","w",stdout);#endifwhile(scanf("%d %d %d\n",&W,&H,&N)==3&&N) {
     for(int i=0;i<H;i++)fgets(Map[i],20,stdin);//注意使用fgets读入，因为gets在C++5.3.0中已被删除Prepare();BuildGraph();printf("%d\n",BFS());}return 0; }