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;
}题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。