本文主要是介绍1006: Hero In Maze，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目描述
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”。
样例输入
copy
4 4 10
....
....
....
S**P
0 0 0样例输出
YES
解决代码：
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZEH 30
#define MAXSIZE 400typedef struct {int i,j;int pre;
}Point;//点的结构体typedef struct{Point data[MAXSIZE];int front,rear;
}Queue;//存放点的队列int initQueue(Queue *queue);//初始化队列
int insQueue(Queue *queue,Point point);//元素进队
int outQueue(Queue *queue,Point *point);//元素出队
int isQueueEmpty(Queue queue);//判断队是否为空int main() {Queue queue;initQueue(&queue);Point start,end;//定义迷宫的起点和终点start.i=start.j=start.pre=-1;//初始化起始点end.i=end.j=end.pre=-1;//初始化终点int m,n,t;int i,j;int flag=0;//标志是否找到路径int map[MAXSIZEH][MAXSIZEH];//存放地图scanf("%d %d %d",&n,&m,&t);//输入迷宫的行，列和getchar();do{//输入地图for(i=0;i<m;i++){for(j=0;j<n;j++){scanf("%c",&map[i][j]);if(map[i][j]=='S'){//找出起点start.i=i;start.j=j;start.pre=-2;}if(map[i][j]=='P'){//找到终点end.i=i;end.j=j;end.pre=-2;}}getchar();}if (end.pre!=-2||start.pre!=-2){//如果找不到起点或者终点结束程序printf("输入有误！！！\n");return 0;} else{printf("输入无误，程序执行！！！\n");}insQueue(&queue,start);//将起点进队Point nowPoint;// int k=0;while (!isQueueEmpty(queue)){//队不为空时循环// k++;// printf("程序执行%d次\n",k);outQueue(&queue,&nowPoint);//出队if(nowPoint.i==end.i&&nowPoint.j==end.j){//如果找到终点，结束查找flag=1;break;}for(i=0;i<4;i++){//四种情况，对当前点的上下左右分别查找符合条件进队Point *a;a=(Point*)malloc(sizeof(Point));*a=nowPoint;switch (i){case 1:a->i++;break;case 2:a->j++;break;case 3:a->i--;break;case 4:a->j--;break;}if(a->i>=0&&a->i<m&&a->j>=0&&a->j<n){if(map[a->i][a->j]=='.'||map[a->i][a->j]=='P'){a->pre=queue.front;insQueue(&queue,*a);}}free(a);}}nowPoint=queue.data[queue.front];// printf("输入的路径\n");int key=0;//计算路径长度while (nowPoint.pre>=0){key++;//printf("I:%d J:%d pre:%d\n",nowPoint.i,nowPoint.j,nowPoint.pre);nowPoint=queue.data[nowPoint.pre];}//printf("%d",key);if(flag==0){printf("NO\n");} else{if(key<=t)//与时间比较printf("YES\n");else{printf("NO\n");}}scanf("%d %d %d",&n,&m,&t);getchar();}while(!(m==0&&n==0&&t==0));return 0;
}int initQueue(Queue *queue){queue->front=-1;queue->rear=-1;return 1;
}int insQueue(Queue *queue,Point point){if(queue->rear+1>=MAXSIZE){return 0;} else{queue->rear+=1;queue->data[queue->rear]=point;}return 1;
}int outQueue(Queue *queue,Point *point){if(queue->front==queue->rear){return 0;} else{queue->front++;*point=queue->data[queue->front];return 1;}
}
int isQueueEmpty(Queue queue){//返回真为空，返回假为不空if(queue.front==queue.rear){return 1;} else{return 0;}
}
这篇关于1006: Hero In Maze的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
