前言

最近学了各种高级的搜索算法后,然后就忍不住想做几道题，这道题搞了我老半天……

题目

描述

You are working for an amusement park as an operator of an obakeyashiki, or a haunted house, in
which guests walk through narrow and dark corridors. The house is proud of their lively ghosts, which are actually robots remotely controlled by the operator, hiding here and there in the corridors. One morning, you found that the ghosts are not in the positions where they are supposed to be. Ah,yesterday was Halloween. Believe or not, paranormal spirits have moved them around the corridors in the night. You have to move them into their right positions before guests come. Your manager is eager to know how long it takes to restore the ghosts. In this problem, you are asked to write a program that, given a floor map of a house, finds the smallest number of steps to move all ghosts to the positions where they are supposed to be. A floor consists of a matrix of square cells. A cell is either a wall cell where ghosts cannot move into or a corridor cell where they can. At each step, you can move any number of ghosts simultaneously. Every ghost can either stay in the current cell, or move to one of the corridor cells in its 4-neighborhood (i.e. immediately left, right,up or down), if the ghosts satisfy the following conditions:
1. No more than one ghost occupies one position at the end of the step.
2. No pair of ghosts exchange their positions one another in the step.
For example, suppose ghosts are located as shown in the following (partial) map, where a sharp
sign (‘#’) represents a wall cell and ‘a’, ‘b’, and ‘c’ ghosts.

####ab#
#c##
####

The following four maps show the only possible positions of the ghosts after one step.

#### #### #### ####
ab # a b# acb# ab #
#c## #c## # ## #c##
#### #### #### ####

Input
The input consists of at most 10 datasets, each of which represents a floor map of a house. The format
of a dataset is as follows.
w h n
c[1][1] c[1][2]… c[1][w]
c[2][1] c[2][2]…c[2][w]
…
c[h][1] c[h][2]… c[h][w]
w, h and n in the first line are integers, separated by a space. w and h are the floor width and height of the house, respectively. n is the number of ghosts. They satisfy the following constraints. 4 ≤ w ≤ 16, 4 ≤ h ≤ 16, 1 ≤ n ≤ 3
Subsequent h lines of w characters are the floor map. Each of cij is either:
? a ‘#’ representing a wall cell,
? a lowercase letter representing a corridor cell which is the initial position of a ghost,
? an uppercase letter representing a corridor cell which is the position where the ghost corresponding to its lowercase letter is supposed to be, or
? a space representing a corridor cell that is none of the above.
In each map, each of the first n letters from a and the first n letters from A appears once and only once. Outermost cells of a map are walls; i.e. all characters of the first and last lines are sharps; and the mfirst and last characters on each line are also sharps. All corridor cells in a map are connected; i.e. given a corridor cell, you can reach any other corridor cell by following corridor cells in the 4-neighborhoods.
Similarly, all wall cells are connected. Any 2 × 2 area on any map has at least one sharp. You can assume that every map has a sequence of moves of ghosts that restores all ghosts to the positions where they are supposed to be. The last dataset is followed by a line containing three zeros separated by a space.
Output
For each dataset in the input, one line containing the smallest number of steps to restore ghosts into
the positions where they are supposed to be should be output. An output line should not contain extra
characters such as spaces.
Sample Input

5 5 2
#####
#A#B#
# #
#b#a#
#####
16 4 3
################
## ########## ##
# ABCcba #
################
16 16 3
################
### ## # ##
## # ## # c#
# ## ########b#
# ## # # # #
# # ## # # ##
## a# # # # #
### ## #### ## #
## # # # #
# ##### # ## ##
#### #B# # #
## C# # ###
# # # ####### #
# ###### A## #
# # ##
################
0 0 0

Sample Output

7
36
77

翻译

就是输入多个h*w的字符矩阵,和n个小鬼(4≤w≤16,4≤h≤16,1≤n≤3)，每个小鬼可以同时移动,也可以不动,但同一时刻不能有多个小鬼出现在同一空格上，当然不能也走’#’，求每个小鬼都回家的最短时间(一个小鬼可以经过另一小鬼的家)。最重要的一点, 每2*2的子矩阵中必有一’#’

分析

相信大家都很容易看出这是一道BFS搜索题,同时三个小鬼可以一起动是个十分麻烦的问题,意味着你每次枚举更新状态时差不多要用5^3，而你看到样例第3个数据可能觉得头都大了。
那么我们就不得不使用双向BFS了，BFS是用(优先)队列来进行搜索的,双向BFS是起点和终点一起搜索,我的做法是将两个初始状态Push进同一个队列里，同时给这两个状态一个Flag来区别,再用一个Vector的Hash数组来进行映射状态,这个关键字Key我之前是将每个字母所在i行j列并在一起来弄的(用CBA的顺序)，比如说样例3中用小写来映射起始位置就是‘031504150705’,终止位置就是’120511091411’，但发现极端情况会有161616151614,用int不行,要用longlong.

#include<set>
#include<map>
#include<cmath>
#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
#include<climits>
#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 16
#define LL long long
#define MOD 100003
#define INF 0x3f3f3f3f
int read(){int f=1,x=0;char c=getchar();while(c<'0'||'9'<c){
   if(c=='-')f=-1;c=getchar();}while('0'<=c&&c<='9'){x=x*10+c-'0';c=getchar();} return f*x;
}
const int Pow[10]={
   1,10,100,1000,10000,100000,1000000,10000000,100000000};
struct node{int t,f,num;node(){}node(int T,int N,int F){t=T,num=N,f=F;}
};
queue<node> Q;
vector<int> G[200];
vector<node> Hash[MOD];
int change[1700],len;
char Map[MAXN+5][MAXN+5],m[5]=" abc";
int w,h,n,s[4][2],e[4][2],dir[5][2]={
   {
   0,0},{
   1,0},{
   0,1},{-1,0},{
   0,-1}},str[4];
int MakeNum(int x[][2]){int ret=0;for(int i=1;i<=n;i++)ret+=Pow[3*(i-1)]*change[100*x[i][0]+x[i][1]];return ret;
}
int Hash_Insert(node x){int tmp=x.num%MOD;for(int i=0;i<int(Hash[tmp].size());i++){node v=Hash[tmp][i];if(x.num==v.num){if(x.f==v.f)return 0;printf("%d\n",x.t+v.t);return 2;}}Hash[tmp].push_back(x);return 1;
}
bool Make(int d,int num,bool from,int t){if(!d){int pan[4]={
   0,num%1000,num/1000%1000,num/1000000};for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++)if((pan[i]==str[j]&&pan[j]==str[i])||pan[i]==pan[j])return 0;node New(t,num,from);int tmp=Hash_Insert(New);if(tmp==2)return 1;else if(tmp==1)Q.push(New);return 0;}int siz=int(G[str[d]].size());for(int i=0;i<siz;i++)if(Make(d-1,num*1000+G[str[d]][i],from,t))return 1;return 0;
}
void BFS(){node now,S(0,MakeNum(s),0),E(0,MakeNum(e),1);Hash_Insert(S),Hash_Insert(E);Q.push(S),Q.push(E);while(!Q.empty()){now=Q.front(),Q.pop();str[1]=now.num%1000,str[2]=now.num/1000%1000,str[3]=now.num/1000000;if(Make(n,0,now.f,now.t+1))return ;}return ;
}
bool vis[200];
void DFS(int nx,int ny,int num){if(vis[num])return ;vis[num]=1;int x,y;for(int i=0;i<=4;i++){x=nx+dir[i][0],y=ny+dir[i][1];if(x<=0||y<=0||x>w||y>h||Map[x][y]=='#'||((x!=nx||y!=ny)&&vis[change[100*x+y]]))continue;G[num].push_back(change[100*x+y]);if(i){G[change[100*x+y]].push_back(num);DFS(x,y,change[100*x+y]);}}return ;
}
int main(){
   //cba CBAwhile(1){len=0;memset(G,0,sizeof G);memset(vis,0,sizeof vis);memset(Map,0,sizeof Map);memset(Hash,0,sizeof Hash);memset(change,0,sizeof change);while(!Q.empty())Q.pop();h=read(),w=read(),n=read();if(!w&&!h&&!n)return 0;for(int i=1;i<=w;i++){fgets(Map[i]+1,MAXN+5,stdin);for(int j=1;j<=h;j++){if(Map[i][j]!='#')change[100*i+j]=++len;if(Map[i][j]!='#'&&Map[i][j]!=' ')for(int k=1;k<=3;k++){if(m[k]==Map[i][j]){s[k][0]=i,s[k][1]=j;break;}else if(m[k]-'a'+'A'==Map[i][j]){e[k][0]=i,e[k][1]=j;break;}}}}for(int i=1;i<=w;i++)for(int j=1;j<=h;j++)if(Map[i][j]!='#'&&(!vis[change[100*i+j]]))DFS(i,j,change[100*i+j]);BFS();}return 0;
}