现在的位置: 首页 > 综合 > 正文

SWUN 1439 – 苦逼的生活刚刚开始

2013年01月06日 ⁄ 综合 ⁄ 共 2757字 ⁄ 字号 评论关闭


苦逼的生活刚刚开始

时间限制(普通/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
.C.
H.W
#M#
3 3
C..
###
HWM

样例输出

3
-1

提示

 

题目来源

CHC

 

题目地址:

http://218.194.91.48/acmhome/problemdetail.do?&method=showdetail&id=1439

 

我出的题。。。

 

BFS+状态压缩

 

这题是寻宝问题的一个转化(可以参照【搜索】走路 - 1018)。

 

理解题意之后,我们可以发现,其实所有可以走的情况,就只有一下两种:

 

HLY – WSX – M – CHC

HLY – M – WSX – CHC

 

并且,必然在6条“”中的某条(包括端点)相遇。

 

那么,我们可以将WSXM当作宝石1和宝石2,以CHC或者HLY为起点,另一个作为终点,把这题当作寻找宝石问题。最后时间除以2,就是我们要的结果了(因为HLYCHC分头出发,最短时间汇合,必然需要走最短路线。于是
HLY
到汇合地点的最短路线 + CHC到汇合地点的最短路线 = HLYCHC的最短路线)。

 

那么接下来做就很容易了。

 

简单的BFS搜索。只不过记录路径的时候,需要增设一维来表示拿到宝石的状态。

 

vis[x][y][拿到的宝石状态]

 

那么有以下4种情况:

 

            未拿到宝石:vis[x][y][0(二进制00)]

            只拿到宝石1vis[x][y][1(二进制01)]

            只拿到宝石2vis[x][y][2(二进制10)]

            两个宝石都拿到:vis[x][y][3(二进制11)]

 

       即用二进制的每一位表示拿到宝石的状态,0表示未拿到,1表示已拿到。

 

以此进行搜索,就能找到答案。

 

当然,这题还有一个Trick,(可以参照【搜索】走路 - 1001),如果HLYCHC相差偶数步,那么他们就可能碰头;但是如果HLYCHC相差奇数步,那么他们永远无法碰头。

(题目中含有这句: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;
}

 

抱歉!评论已关闭.