【BFS】The Morning after Halloween
Time Limit: 8000MS | Memory Limit: 65536K | |
Total Submissions: 2395 | Accepted: 543 |
Description
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:
No more than one ghost occupies one position at the end of the step.
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.
#### |
#### |
#### |
#### |
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 | |
c11 | c12 | ⋯ | c1w |
c21 | c22 | ⋯ | c2w |
⋮ | ⋮ | ⋱ | ⋮ |
ch1 | ch2 | ⋯ | chw |
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 first 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
Source
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<algorithm> using namespace std;
inline int read(){
int x=0,f=1;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
for(;isdigit(c);c=getchar()) x=x*10+c-'0';
return x*f;
}
const int INF = 9999999;
const int MAXN = 100000;
int N,M,K;
char MP[17][17];
int Ax,Ay; int Bx,By; int Cx,Cy;
int ax,ay; int bx,by; int cx,cy;
int vis[151][151][151];
int visB[151][151][151];
struct data{
int ax,ay;
int bx,by;
int cx,cy;
int stp;
}que[1000001];
struct data2{
int Ax,Ay;
int Bx,By;
int Cx,Cy;
int stp;
}que2[1000001];
int dis[6][2]={{0,1},{1,0},{0,-1},{-1,0},{0,0}}; int ls=1,rs=0;
int lb=1,rb=0;
int dit[21][21];
void in(int axx,int ayy,int bxx,int byy,int cxx,int cyy,int sp,bool fg){
if(!fg){
vis[dit[axx][ayy]][dit[bxx][byy]][dit[cxx][cyy]]=sp;
que[++rs].ax=axx;
que[rs].ay=ayy;
que[rs].bx=bxx;
que[rs].by=byy;
que[rs].cx=cxx;
que[rs].cy=cyy;
que[rs].stp=sp;
}
else{
visB[dit[axx][ayy]][dit[bxx][byy]][dit[cxx][cyy]]=sp;
que2[++rb].Ax=axx;
que2[rb].Ay=ayy;
que2[rb].Bx=bxx;
que2[rb].By=byy;
que2[rb].Cx=cxx;
que2[rb].Cy=cyy;
que2[rb].stp=sp;
}
}
int ans;
bool flag=false; void BFS(){
in(ax,ay,bx,by,cx,cy,0,0);
in(Ax,Ay,Bx,By,Cx,Cy,0,1);
int x1,y1,x2,y2,x3,y3,sp;
int t=0;
while(ls<=rs&&lb<=rb){
if(flag) t++;
if(t>1024) break;
x1=que[ls].ax;
y1=que[ls].ay;
x2=que[ls].bx;
y2=que[ls].by;
x3=que[ls].cx;
y3=que[ls].cy;
sp=que[ls].stp;
//cout<<"S:"<<x1<<" "<<y1<<" "<<x2<<" "<<y2<<" "<<x3<<" "<<y3<<" "<<sp<<endl;
for(int i=0;i<5;i++){
int xx1=x1+dis[i][0];
int yy1=y1+dis[i][1];
if(xx1>N||yy1>M||yy1<1||xx1<1) continue;
if(MP[xx1][yy1]=='#') continue;
if(x2||y2)
for(int j=0;j<5;j++){
int xx2=x2+dis[j][0];
int yy2=y2+dis[j][1];
if(xx2==xx1&&yy1==yy2) continue;
if(xx2>N||yy2>M||xx2<1||yy2<1) continue;
if(xx2==x1&&yy2==y1&&xx1==x2&&yy1==y2) continue;
if(MP[xx2][yy2]=='#') continue;
if(x3||y3)
for(int k=0;k<5;k++){
if(i==4&&j==4&&k==4) continue;
int xx3=x3+dis[k][0];
int yy3=y3+dis[k][1];
if(xx2==x3&&yy2==y3&&xx3==x2&&yy3==y2) continue;
if(xx3==x1&&yy3==y1&&xx1==x3&&yy1==y3) continue;
if((xx3==xx1&&yy3==yy1)||(xx3==xx2&&yy3==yy2)) continue;
if(xx3>N||yy3>M||xx3<1||yy3<1||vis[dit[xx1][yy1]][dit[xx2][yy2]][dit[xx3][yy3]]!=-1) continue;
if(MP[xx3][yy3]=='#') continue;
if(visB[dit[xx1][yy1]][dit[xx2][yy2]][dit[xx3][yy3]]!=-1){
ans=min(visB[dit[xx1][yy1]][dit[xx2][yy2]][dit[xx3][yy3]]+sp+1,ans);
flag=true;// return ;
}
in(xx1,yy1,xx2,yy2,xx3,yy3,sp+1,0);
}
else{
if(vis[dit[xx1][yy1]][dit[xx2][yy2]][dit[x3][y3]]!=-1) continue;
if(i==4&&j==4) continue;
//cout<<"tmp:"<<xx1<<" "<<yy1<<" "<<xx2<<" "<<yy2<<endl;
if(visB[dit[xx1][yy1]][dit[xx2][yy2]][dit[x3][y3]]!=-1){
ans=min(visB[dit[xx1][yy1]][dit[xx2][yy2]][dit[x3][y3]]+sp+1,ans);
flag=true; //return ;
}
in(xx1,yy1,xx2,yy2,x3,y3,sp+1,0);
}
}
else{
if(vis[dit[xx1][yy1]][dit[x2][y2]][dit[x3][y3]]!=-1) continue;
if(i==4) continue;
if(visB[dit[xx1][yy1]][dit[x2][y2]][dit[x3][y3]]!=-1){
ans=min(visB[dit[xx1][yy1]][dit[x2][y2]][dit[x3][y3]]+sp+1,ans);
flag=true; //return ;
}
in(xx1,yy1,x2,y2,x3,y3,sp+1,0);
}
} x1=que2[lb].Ax;
y1=que2[lb].Ay;
x2=que2[lb].Bx;
y2=que2[lb].By;
x3=que2[lb].Cx;
y3=que2[lb].Cy;
sp=que2[lb].stp;
//cout<<"B:"<<x1<<" "<<y1<<" "<<x2<<" "<<y2<<" "<<x3<<" "<<y3<<" "<<sp<<endl;
for(int i=0;i<5;i++){
int xx1=x1+dis[i][0];
int yy1=y1+dis[i][1];
if(xx1>N||yy1>M||yy1<1||xx1<1) continue;
if(MP[xx1][yy1]=='#') continue;
if(x2||y2)
for(int j=0;j<5;j++){
int xx2=x2+dis[j][0];
int yy2=y2+dis[j][1];
if(xx2==x1&&yy2==y1&&xx1==x2&&yy1==y2) continue;
if(xx2==xx1&&yy1==yy2) continue;
if(xx2>N||yy2>M||xx2<1||yy2<1) continue;
if(MP[xx2][yy2]=='#') continue;
if(x3||y3)
for(int k=0;k<5;k++){
if(i==4&&j==4&&k==4) continue;
int xx3=x3+dis[k][0];
int yy3=y3+dis[k][1];
if(xx2==x3&&yy2==y3&&xx3==x2&&yy3==y2) continue;
if(xx3==x1&&yy3==y1&&xx1==x3&&yy1==y3) continue;
if((xx3==xx1&&yy3==yy1)||(xx3==xx2&&yy3==yy2)) continue;
if(xx3>N||yy3>M||xx3<1||yy3<1||visB[dit[xx1][yy1]][dit[xx2][yy2]][dit[xx3][yy3]]!=-1) continue;
if(MP[xx3][yy3]=='#') continue;
if(vis[dit[xx1][yy1]][dit[xx2][yy2]][dit[xx3][yy3]]!=-1){
ans=min(vis[dit[xx1][yy1]][dit[xx2][yy2]][dit[xx3][yy3]]+sp+1,ans);
flag=true; //return ;
}
in(xx1,yy1,xx2,yy2,xx3,yy3,sp+1,1);
}
else{
if(visB[dit[xx1][yy1]][dit[xx2][yy2]][dit[x3][y3]]!=-1) continue;
if(i==4&&j==4) continue;
//cout<<"tmp:"<<xx1<<" "<<yy1<<" "<<xx2<<" "<<yy2<<" "<<sp+1<<endl;
if(vis[dit[xx1][yy1]][dit[xx2][yy2]][dit[x3][y3]]!=-1){
ans=min(vis[dit[xx1][yy1]][dit[xx2][yy2]][dit[x3][y3]]+sp+1,ans);
flag=true; //return ;
}
in(xx1,yy1,xx2,yy2,x3,y3,sp+1,1);
}
}
else{
if(visB[dit[xx1][yy1]][dit[x2][y2]][dit[x3][y3]]!=-1) continue;
if(i==4) continue;
if(vis[dit[xx1][yy1]][dit[x2][y2]][dit[x3][y3]]!=-1){
ans=min(vis[dit[xx1][yy1]][dit[x2][y2]][dit[x3][y3]]+sp+1,ans);
flag=true; //return ;
}
in(xx1,yy1,x2,y2,x3,y3,sp+1,1);
}
}
ls++,lb++;
}
} int main(){
//freopen("a.txt","w",stdout);
while(1){
M=read(),N=read(),K=read();
if(!N||!M) break;
Ax=Ay=Bx=By=Cx=Cy=ax=ay=bx=by=cx=cy=0;
ls=1,rs=0;
lb=1,rb=0;
for(int i1=0;i1<=150;i1++)
for(int i2=0;i2<=150;i2++)
for(int i3=0;i3<=150;i3++){
vis[i1][i2][i3]=-1;
visB[i1][i2][i3]=-1;
}
int cnt=0;
for(int i=1;i<=N;i++){
for(int j=1;j<=M;j++){
MP[i][j]=getchar();
if(MP[i][j]=='A') Ax=i,Ay=j;
if(MP[i][j]=='B') Bx=i,By=j;
if(MP[i][j]=='C') Cx=i,Cy=j;
if(MP[i][j]=='a') ax=i,ay=j;
if(MP[i][j]=='b') bx=i,by=j;
if(MP[i][j]=='c') cx=i,cy=j;
if(MP[i][j]!='#'){
dit[i][j]=++cnt;
}
}
getchar();
}
ans=INF; flag=false;
BFS();
cout<<ans<<endl;
}
}
最新文章
- [转]说说JSON和JSONP,也许你会豁然开朗,含jQuery用例
- 主机和虚拟机能相互ping通但是不能复制
- 2.4---把链表划分为两部分(CC150)
- 后台session过期,tomcat重启,自动跳转页面js写法
- MathType的公式在word中跟文字不对齐
- 表单的enctype property
- 使用HIBERNATE的SQL查询并将结果集自动转换成POJO
- 数组去重算法,quickSort
- 使用 Tomcat 7 新的连接池 —— Tomcat jdbc pool
- Demo学习: CellDraw
- 我的第一个项目:用kinect录视频库
- ssh远程登录linux live系统
- 本地php 连接 MySQL
- 实战DeviceIoControl 之三:制作磁盘镜像文件
- 华为oj之字符个数统计
- adobe air for ios 例子
- 帝国cms用户密码忘记怎么修改
- SQLUnit 环境搭建
- Socket编程:之双机通信
- swift-Xcode7.x(7.1,7.2,7.3)新建playground运行不能运行
热门文章
- vuejs怎么在服务器部署?
- 寻找kernel32.dll的地址
- java===java基础学习(4)---字符串操作
- problems when installed mysql in linux ubuntu
- 【openjudge】C15C Rabbit&#39;s Festival CDQ分治+并查集
- 面试题之堆栈队列系列一:设计包含min函数的栈
- Windows + IDEA 手动开发MapReduce程序
- yum 安装 jdk
- 微信小程序实战篇-下拉刷新与加载更多
- 【转载】关于Python的Mixin模式