【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版的读者请点这里。

相信大家都清楚了本题的思路，所以这里只简述一下双向BFS的注意的地方。

首先，我们必须注意，双向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]; int col[Maxn+5][Maxn+5][Maxn+5]; queue<int> q[2];inline void clear() {
     memset(d,-1,sizeof d);memset(col,-1,sizeof col);while(!q[0].empty())q[0].pop();while(!q[1].empty())q[1].pop(); } 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; } inline int BFS(int id) {
     int siz=q[id].size();while(siz--) {
     int u=q[id].front();q[id].pop();int a=(u>>16)&0xFF,b=(u>>8)&0xFF,c=u&0xFF;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(col[ta][tb][tc]==-1) {
     col[ta][tb][tc]=id;d[ta][tb][tc]=d[a][b][c]+1;q[id].push(getid(ta,tb,tc));} else if(col[ta][tb][tc]==(!id))return d[ta][tb][tc]+d[a][b][c];}}}}return -1; } int BFS() {
     clear();q[0].push(getid(s[0],s[1],s[2]));q[1].push(getid(t[0],t[1],t[2]));d[s[0]][s[1]][s[2]]=0;d[t[0]][t[1]][t[2]]=1;col[s[0]][s[1]][s[2]]=0;col[t[0]][t[1]][t[2]]=1;while(!q[0].empty()||!q[1].empty()) {
     int t=BFS(0);if(t!=-1)return t;t=BFS(1);if(t!=-1)return t;}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);Prepare();BuildGraph();printf("%d\n",BFS());}return 0; }