问题 21929 --数据结构/栈和队列/迷宫寻宝

21929: 数据结构/栈和队列/迷宫寻宝

时间限制: 1 Sec  内存限制: 32 MB
提交: 80  解决: 17
[提交][状态][讨论版][数据上传:][下载FPS1元][下载测试数据1元][20kb]

题目描述

实验目的:

  1、熟悉队列的实现和使用;

  2、掌握一种路径搜索算法;

实验原理:

  1、队列的原理:略

  2、路径搜索算法的原理:利用队列记忆已经达到过,但还未展开搜索的地点,可以将所有地点无遗漏无重复的搜索到。

实验步骤:

  1、定义坐标点类;

  2、定义实现循环队列类,该类要求可以存储若干个坐标点。

  3、利用队列实现路径搜索算法。

  4、完成输入输出控制。

 

程欣宇 2014年4月13日编写

输入

输入由多个迷宫组成,每个迷宫开始一行是两个数字n和m,表示迷宫的行列数量

接下来的n行是迷宫的字符图案。

图案中的字符B表示可能的宝箱,空格表示可以走动的空间,其它字符表示障碍物

图案的行列坐标是以0开始计算的,坐标x=1,y=0处一定是迷宫出入口

输出

对应每个迷宫,应该有一行输出

如果找到宝箱,输出为:Box is found at x=宝箱x坐标 y=宝箱y坐标.

如果找不到宝箱,输出为:Box is not found.

样例输入

4 4
0 23
1 BN
2  N
3NNN
4 4
0 23
1 XN
2XBN
3NNN
11 12
0 234567890N
1  N       N
2  N B     N
3   NNNNNNNN
4          N
5    NNNNNNN
6    NB    N
7N NNNNNN  N
8N         N
9BN        N
NNNNNNNNNNNN

样例输出

Box is found at x=2 y=1.
Box is not found.
Box is found at x=6 y=6.

提示


1、输入和地图存储结构提示,参考如下代码:



#define N 101 //最大行列数

char map[N][N];



int n,m;//行列数



int main()

{



 while(scanf("%d%d\n",&n,&m)==2)//能够读到两个数字说明还有输入要处理

 {



  for (int i=0;i<n;i++)

   gets(map[i]);//读取第i行

  map[0][1]='N';//封住出口



  //TODO:已经拿到迷宫地形图,调用自己实现的迷宫寻宝算法

 }

 return 0;

}



2、坐标点结构体定义


struct Point{

 int x,y;

 Point(int x=0,int y=0){

  this->x=x;

  this->y=y;

 }

};


3、支持任意元素类型的模板循环队列定义



template<class T>

struct Queue{

 T items[N*N];

 int tail; //队尾指针

 int front; //队首指针

 

 Queue() {  tail=0;  front=0; }



 bool Push(T &item) {//TODO:自己实现}



 bool Pop(T &item) {//TODO:自己实现}

 bool isEmpty() {//TODO:自己实现 }

};



4、利用坐标队列遍历迷宫可以达到的所有位置



 



把迷宫入口加入坐标队列



while(队列非空)



{



    坐标 p=队列出队一个元素;



    考察地图中p坐标的上下左右的情况:



   如果是'B',则表示找到宝箱,输出并返回



   如果是空格,则表示尚未走到过,在地图上标记该位置,然后将坐标入队



}



 

来源

[提交][状态]