11761: 数据结构/栈和队列/迷宫寻宝
Description
实验目的：
１、熟悉队列的实现和使用；
２、掌握一种路径搜索算法；
实验原理：
１、队列的原理：略
２、路径搜索算法的原理：利用队列记忆已经达到过，但还未展开搜索的地点，可以将所有地点无遗漏无重复的搜索到。
实验步骤：
１、定义坐标点类；
２、定义实现循环队列类，该类要求可以存储若干个坐标点。
３、利用队列实现路径搜索算法。
４、完成输入输出控制。
程欣宇 ２０１４年４月１３日编写
Input
输入由多个迷宫组成，每个迷宫开始一行是两个数字n和m，表示迷宫的行列数量
接下来的n行是迷宫的字符图案。
图案中的字符B表示可能的宝箱，空格表示可以走动的空间，其它字符表示障碍物
图案的行列坐标是以0开始计算的，坐标x=1,y=0处一定是迷宫出入口
Output
对应每个迷宫，应该有一行输出
如果找到宝箱，输出为：Box is found at x=宝箱x坐标 y=宝箱y坐标.
如果找不到宝箱，输出为：Box is not found.
Sample Input Copy
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
Sample Output Copy
Box is found at x=2 y=1.
Box is not found.
Box is found at x=6 y=6.HINT
１、输入和地图存储结构提示，参考如下代码：
#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'，则表示找到宝箱，输出并返回
如果是空格，则表示尚未走到过，在地图上标记该位置，然后将坐标入队
}