苦逼的生活刚刚开始时间限制(普通/Java) : 1000 MS/ 3000 MS 运行内存限制 : 65536 KByte
总提交 : 17 测试通过 : 5 描述
暑假刷了两个月的副本,遭遇各种恶心、坑爹、坑妹的战役,然而苦逼的生活才刚刚开始,真正的战斗才刚刚开始!
这一天,HLY、CHC、WSX即将奔赴战场,HLY与CHC早早便起来准备,但是WSX仍在梦中风卷残云般大吃大喝。当然,HLY早就打过了WSX电话,无奈WSX的电话已经关机。 经询问,得知WSX躲在学校某个阴暗的地方睡觉。于是CHC和HLY从各自的住处出发,分头寻找WSX,而先找到WSX的人,则带着WSX去与另一个汇合。 然而,又一个问题出现了,CHC和HLY发现模板没有带!模板被放在机房了!!!这可是居家必备,上战场可乱砍的利器!!!于是,在CHC与HLY寻找WSX的过程中,必须有一个人抽空去拿模板。(比如CHC去拿模板,再找到WSX,然后去和HLY汇合;或者CHC找到WSX,然后带着WSX去拿模板,然后和HLY汇合;或者CHC找WSX,HLY拿模板,然后三人汇合;以CHC类推HLY。)
现在给你一张学校地图。“.”代表某个地点(比如:BS-330、B7-5-1-7 或者 BC-1-WC),“#”代表障碍(因此CHC或HLY或WSX遇到它时,必须绕路走),H代表HLY的初始位置、C代表CHC的初始位置、W代表WSX睡觉的地方、M代表机房位置。
已知CHC或HLY从某个地点走到另一个相邻地点(上、下、左、右 方向,并且只能走这四个方向)需要花费1个单位的时间(当然,带着WSX走的时候,速度是不变的),并且由于急着赶赴战场,CHC或HLY都不会在某个地点停留超过1个单位的时间(即第t时到达某地,第t+1时就一定会离开。带着模板或者带着WSX时,也一样)。
现在问题来了,请你回答,他们能否在某个地点汇合?如果可以汇合,那么汇合所需要的时间最短是多少?
输入
多组测试数据(Case<=20)。 每组测试数据,第一行输入两个整数n和m,代表地图的大小(1<=n,m<=100 并且 n*m>=4)。 接下去n行,每行m个字母,代表地图。
输出
对于每组测试数据,如果HLY、CHC能够拿到模版,并且找到WSX然后在某个地点汇合,并且,那么输出他们汇合所需要的最短时间,否则,请输出-1 。 样例输入 3 3 样例输出 3 提示
题目来源 CHC |
http://218.194.91.48/acmhome/problemdetail.do?&method=showdetail&id=1439
我出的题。。。
BFS+状态压缩
这题是寻宝问题的一个转化(可以参照【搜索】走路 - 1018)。
理解题意之后,我们可以发现,其实所有可以走的情况,就只有一下两种:
HLY – WSX – M – CHC
HLY – M – WSX – CHC
并且,必然在6条“–”中的某条(包括端点)相遇。
那么,我们可以将WSX和M当作宝石1和宝石2,以CHC或者HLY为起点,另一个作为终点,把这题当作寻找宝石问题。最后时间除以2,就是我们要的结果了(因为HLY和CHC分头出发,最短时间汇合,必然需要走最短路线。于是
HLY到汇合地点的最短路线 + CHC到汇合地点的最短路线 = HLY到CHC的最短路线)。
那么接下来做就很容易了。
简单的BFS搜索。只不过记录路径的时候,需要增设一维来表示拿到宝石的状态。
vis[x][y][拿到的宝石状态]
那么有以下4种情况:
未拿到宝石:vis[x][y][0(二进制00)]
只拿到宝石1:vis[x][y][1(二进制01)]
只拿到宝石2:vis[x][y][2(二进制10)]
两个宝石都拿到:vis[x][y][3(二进制11)]
即用二进制的每一位表示拿到宝石的状态,0表示未拿到,1表示已拿到。
以此进行搜索,就能找到答案。
当然,这题还有一个Trick,(可以参照【搜索】走路 - 1001),如果HLY和CHC相差偶数步,那么他们就可能碰头;但是如果HLY和CHC相差奇数步,那么他们永远无法碰头。
(题目中含有这句:CHC或HLY都不会在某个地点停留超过1个单位的时间)
#include<iostream> #include<cstdio> #include<cstring> struct Node{ int x,y,v; Node(){} Node(int xx,int yy,int vv){ x=xx; y=yy; v=vv; } }que[100000]; int vis[103][103][4]; int fx[]={1,-1,0,0}; int fy[]={0,0,1,-1}; int n,m; char mp[103][103]; int hx,hy,cx,cy; int bfs(){ int s,t,k; int x,y,v,nx,ny,nv; if((hx-cx+hy-cy)&1) return -1; memset(vis,-1,sizeof(vis)); que[s=t=0]=Node(hx,hy,0); vis[hx][hy][0]=0; while(s<=t){ if(vis[cx][cy][3]!=-1){ return vis[cx][cy][3]/2; } x=que[s].x; y=que[s].y; v=que[s].v; s++; for(k=0;k<4;k++){ nx=x+fx[k]; ny=y+fy[k]; nv=v; if(nx<0 || ny<0 || nx>=n || ny>=m) continue; if(mp[nx][ny]=='#') continue; if(mp[nx][ny]=='W') nv|=1; else if(mp[nx][ny]=='M') nv|=2; if(vis[nx][ny][nv]!=-1) continue; vis[nx][ny][nv]=vis[x][y][v]+1; que[++t]=Node(nx,ny,nv); } } return -1; } int input(){ int i,j; if(scanf("%d%d",&n,&m)==-1) return 0; for(i=0;i<n;i++){ scanf("%s",mp[i]); for(j=0;j<m;j++) if(mp[i][j]=='H') hx=i,hy=j; else if(mp[i][j]=='C') cx=i,cy=j; } return 1; } int main(){ while(input()){ printf("%d\n",bfs()); } return 0; }