Hero In Maze

Hero In Maze

时间: 1000ms        内存:64M

描述:

500年前,Jesse是我国最卓越的剑客。他英俊潇洒,而且机智过人^_^。
突然有一天,Jesse心爱的公主被魔王困在了一个巨大的迷宫中。Jesse听说这个消息已经是两天以后了,他知道公主在迷宫中还能坚持T天,他急忙赶到迷宫,开始到处寻找公主的下落。 时间一点一点的过去,Jesse还是无法找到公主。最后当他找到公主的时候,美丽的公主已经死了。从此Jesse郁郁寡欢,茶饭不思,一年后追随公主而去了。T_T 500年后的今天,Jesse托梦给你,希望你帮他判断一下当年他是否有机会在给定的时间内找到公主。
他会为你提供迷宫的地图以及所剩的时间T。请你判断他是否能救出心爱的公主。

输入:

题目包括多组测试数据。 每组测试数据以三个整数N,M,T(0<n, m≤20, t>0)开头,分别代表迷宫的长和高,以及公主能坚持的天数。 紧接着有M行,N列字符,由".","*","P","S"组成。其中 "." 代表能够行走的空地。 "*" 代表墙壁,Jesse不能从此通过。 "P" 是公主所在的位置。 "S" 是Jesse的起始位置。 每个时间段里Jesse只能选择“上、下、左、右”任意一方向走一步。 输入以0 0 0结束。

输出:

如果能在规定时间内救出公主输出“YES”,否则输出“NO”。

示例输入:

4 4 10
....
....
....
S**P
0 0 0

示例输出:

YES

提示:

参考答案(内存最优[0]):

#include<iostream>
#include<queue>
#include<memory.h>
using namespace std;

char map[21][21];
int map1[21][21];

struct ma{
	int i;
	int j;
	int step;
};

bool judge(int mai,int maj,int n,int m){
	if(mai>=m||mai<0){
		return false;	
	}
	if(maj>=n||maj<0){
		return false;
	}
	if(map1[mai][maj]==1){
		return false;
	}
	return true;
}
int main()
{
	
	int N,M,T;
	while(1){
		cin>>M>>N>>T;
		if(N==0&&M==0&&T==0){
			break;
		}
		memset(map1,0,sizeof(map1));
		ma maa;
		for(int i=0;i<N;++i){
			for(int j=0;j<M;++j){
				cin>>map[i][j];
				if(map[i][j]=='S'){maa.i=i;maa.j=j;maa.step = 0;map1[i][j]==1;}
				if(map[i][j]=='*'){map1[i][j]=1;}
			}
		}
		queue<ma>ste;
		ste.push(maa);
		int flag = 0;
		while(!ste.empty()){
			
			ma temp = ste.front();
			//temp.i = ste.front().i;
			//temp.j = ste.front().j;
			//temp.step = ste.front().step;
			if(temp.step>T ){
				flag = 1;
				cout<<"NO"<<endl;
				break;
			}
;			if(map[temp.i][temp.j] =='P'){
				if(temp.step<=T  ){
					cout<<"YES"<<endl;flag = 1;
					break;
				}
			}else{
				temp.step+=1;
				if(judge(temp.i-1,temp.j,N,M)){
					temp.i -=1;
					ste.push(temp);
					temp.i+=1;
					map1[temp.i][temp.j]=1;
				}
				if(judge(temp.i,temp.j+1,N,M)){
					temp.j +=1;
					ste.push(temp);
					temp.i-=1;
					map1[temp.i][temp.j]=1;
				}
				if(judge(temp.i+1,temp.j,N,M)){
					temp.i +=1;
					ste.push(temp);
					temp.i-=1;
					map1[temp.i][temp.j]=1;
				}
				if(judge(temp.i,temp.j-1,N,M)){
					temp.j -=1;
					ste.push(temp);
					temp.j+=1;
					map1[temp.i][temp.j]=1;
				}
			}	
			ste.pop();
		}
		if(!flag)cout<<"NO"<<endl;	
	}
	return 0;
}

参考答案(时间最优[0]):

#include<stdio.h>
#include<string.h>
struct node
{
	int x,y;
}que[401];
char visited[21][21];
int xs,ys,xe,ye,head,tail,pt,n,m;
int go[4][2]={{0,1},{1,0},{-1,0},{0,-1}};
int bfs(int x1,int y1,int x2,int y2)
{
	int i,x,y,step=0,k;
	head=pt=0;
	tail=1;
	que[0].x=x1;
	que[0].y=y1;
	while(head<tail)
	{
		pt=tail;
		step++;
		for(k=head;k<tail;k++)
		{
			for(i=0;i<4;i++)
				{
					x=que[k].x+go[i][0];
					y=que[k].y+go[i][1];
					if(x>=0&&x<m&&y>=0&&y<n&&visited[x][y]!='*')
					{
						que[pt].x=x;
						que[pt++].y=y;
						visited[x][y]='*';
					}
					if(x==x2&&y==y2) return step;
				}
		}
		head=tail;
		tail=pt;
	}
	return -1;
}
int main()
{
	int t,res;
	int i,j;
	while(scanf("%d%d%d",&n,&m,&t),n||m||t)
	{
		getchar();
		for(i=0;i<m;i++)
		   gets(visited[i]);
		for(i=0;i<m;i++)
		{		
			for(j=0;j<n;j++)
			{
				if(visited[i][j]=='S')
				{
					xs=i,ys=j;
					visited[i][j]='*';
				}	
				if(visited[i][j]=='P')
					xe=i,ye=j;
			}
			
		}
			res=bfs(xs,ys,xe,ye);
			if(res>-1&&res<=t)printf("YES\n");
			else printf("NO\n");
	}
	return 0;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞