2507 - 数据结构/栈和队列/迷宫寻宝（软件1、2班）
Time Limit : 1 秒
Memory Limit : 12 MB
<span style="font-family:宋体;">实验目的：</span><span style="font-family:'Microsoft Yahei';"> <span></span></span>
<span style="font-family:宋体;"> １、熟悉队列的实现和使用；</span><span style="font-family:'Microsoft Yahei';"> <span></span></span>
<span style="font-family:宋体;"> ２、掌握一种路径搜索算法；</span><span style="font-family:'Microsoft Yahei';"> <span></span></span>
<span style="font-family:宋体;">实验原理：</span><span style="font-family:'Microsoft Yahei';"> <span></span></span>
<span style="font-family:宋体;"> １、队列的原理：略</span><span style="font-family:'Microsoft Yahei';"> <span></span></span>
<span style="font-family:宋体;"> ２、路径搜索算法的原理：利用队列记忆已经达到过，但还未展开搜索的地点，可以将所有地点无遗漏无重复的搜索到。</span><span style="font-family:'Microsoft Yahei';"> <span></span></span>
<span style="font-family:宋体;">实验步骤：</span><span style="font-family:'Microsoft Yahei';"> <span></span></span>
<span style="font-family:宋体;"> １、定义坐标点类；</span><span style="font-family:'Microsoft Yahei';"> <span></span></span>
<span style="font-family:宋体;"> ２、定义实现循环队列类，该类要求可以存储若干个坐标点。</span><span style="font-family:'Microsoft Yahei';"> <span></span></span>
<span style="font-family:宋体;"> ３、利用队列实现路径搜索算法。</span><span style="font-family:'Microsoft Yahei';"> <span></span></span>
<span style="font-family:宋体;"> ４、完成输入输出控制。</span><span style="font-family:'Microsoft Yahei';"> <span></span></span>
Input
<span style="font-family:宋体;">输入由多个迷宫组成，每个迷宫开始一行是两个数字</span><span style="font-family:'Microsoft Yahei';">n</span><span style="font-family:宋体;">和</span><span style="font-family:'Microsoft Yahei';">m</span><span style="font-family:宋体;">，表示迷宫的行列数量</span><span style="font-family:'Microsoft Yahei';"> <span></span></span>
<span style="font-family:宋体;">接下来的</span><span style="font-family:'Microsoft Yahei';">n</span><span style="font-family:宋体;">行是迷宫的字符图案</span>
<span style="font-family:宋体;">图案中的字符</span><span style="font-family:'Microsoft Yahei';">B</span><span style="font-family:宋体;">表示可能的宝箱，空格表示可以走动的空间，其它字符表示障碍物</span><span style="font-family:'Microsoft Yahei';"> <span></span></span>
<span style="font-family:宋体;">图案的行列坐标是以</span><span style="font-family:'Microsoft Yahei';">0</span><span style="font-family:宋体;">开始计算的，坐标</span><span style="font-family:'Microsoft Yahei';">x=1,y=0</span><span style="font-family:宋体;">处一定是迷宫出入口</span><span style="font-family:'Microsoft Yahei';"> <span></span></span>
Output
<span style="font-family:宋体;">对应每个迷宫，应该有一行输出</span><span style="font-family:'Microsoft Yahei';"> <span></span></span>
<span style="font-family:宋体;">如果找到宝箱，输出为：</span><span style="font-family:'Microsoft Yahei';">Box is found at x=</span><span style="font-family:宋体;">宝箱</span><span style="font-family:'Microsoft Yahei';">x</span><span style="font-family:宋体;">坐标</span><span style="font-family:'Microsoft Yahei';"> y=</span><span style="font-family:宋体;">宝箱</span><span style="font-family:'Microsoft Yahei';">y</span><span style="font-family:宋体;">坐标</span><span style="font-family:'Microsoft Yahei';">. </span>
<span style="font-family:宋体;">如果找不到宝箱，输出为：</span><span style="font-family:'Microsoft Yahei';">Box is not found. </span>
Examples
Input Format
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
Output Format
Box is found at x=2 y=1. Box is not found. Box is found at x=6 y=6.
Hint
<span style="font-family:宋体;font-size:9pt;">１、输入和地图存储结构提示，参考如下代码：</span><span style="font-family:Tahoma;font-size:9pt;"></span>
<span style="font-family:Tahoma;font-size:9pt;">#define N 101 //</span><span style="font-family:宋体;font-size:9pt;">最大行列数</span><span style="font-family:Tahoma;font-size:9pt;"><br />
char map[N][N];
<span style="font-family:Tahoma;font-size:9pt;">int n,m;//</span><span style="font-family:宋体;font-size:9pt;">行列数</span><span style="font-family:Tahoma;font-size:9pt;"></span>
<span style="font-family:Tahoma;font-size:9pt;">int main()<br />
{
<span style="font-family:Tahoma;font-size:9pt;"> while(scanf("%d%d\n",&n,&m)==2)//</span><span style="font-family:宋体;font-size:9pt;">能够读到两个数字说明还有输入要处理</span><span style="font-family:Tahoma;font-size:9pt;"><br />
{
<span style="font-family:Tahoma;font-size:9pt;"> for (int i=0;i<n;i++)<br />
gets(map[i]);//读取第i行
map[0][1]='N';//封住出口
<span style="font-family:Tahoma;font-size:9pt;"> //TODO:</span><span style="font-family:宋体;font-size:9pt;">已经拿到迷宫地形图，调用自己实现的迷宫寻宝算法</span><span style="font-family:Tahoma;font-size:9pt;"><br />
}
return 0;
}
<span style="font-family:Tahoma;font-size:9pt;">2</span><span style="font-family:宋体;font-size:9pt;">、坐标点结构体定义</span><span style="font-family:Tahoma;font-size:9pt;"></span>
<span style="font-family:Tahoma;font-size:9pt;">struct Point{<br />
int x,y;
Point(int x=0,int y=0){
this->x=x;
this->y=y;
}
};
<span style="font-family:Tahoma;font-size:9pt;">3</span><span style="font-family:宋体;font-size:9pt;">、支持任意元素类型的模板循环队列定义</span><span style="font-family:Tahoma;font-size:9pt;"></span>
<span style="font-family:Tahoma;font-size:9pt;">template<class T><br />
struct Queue{
T items[N*N];
int tail; //队尾指针
int front; //队首指针
Queue() { tail=0; front=0; }
<span style="font-family:Tahoma;font-size:9pt;"> bool Push(T &item) {//TODO:</span><span style="font-family:宋体;font-size:9pt;">自己实现</span><span style="font-family:Tahoma;font-size:9pt;">}</span>
<span style="font-family:Tahoma;font-size:9pt;"> bool Pop(T &item) {//TODO:</span><span style="font-family:宋体;font-size:9pt;">自己实现</span><span style="font-family:Tahoma;font-size:9pt;">}<br />
bool isEmpty() {//TODO:自己实现 }
};
<span style="font-family:Tahoma;font-size:9pt;">4</span><span style="font-family:宋体;font-size:9pt;">、利用坐标队列遍历迷宫可以达到的所有位置</span><span style="font-family:Tahoma;font-size:9pt;"></span>
<span style="font-family:Tahoma;font-size:9pt;"> </span>
<span style="font-family:宋体;font-size:9pt;">把迷宫入口加入坐标队列</span><span style="font-family:Tahoma;font-size:9pt;"></span>
<span style="font-family:Tahoma;font-size:9pt;">while(</span><span style="font-family:宋体;font-size:9pt;">队列非空</span><span style="font-family:Tahoma;font-size:9pt;">)</span>
<span style="font-family:Tahoma;font-size:9pt;">{</span>
<span style="font-family:Tahoma;font-size:9pt;"> </span><span style="font-family:宋体;font-size:9pt;">坐标</span><span style="font-family:Tahoma;font-size:9pt;"> p=</span><span style="font-family:宋体;font-size:9pt;">队列出队一个元素</span><span style="font-family:Tahoma;font-size:9pt;">;</span>
<span style="font-family:Tahoma;font-size:9pt;"> </span><span style="font-family:宋体;font-size:9pt;">考察地图中</span><span style="font-family:Tahoma;font-size:9pt;">p</span><span style="font-family:宋体;font-size:9pt;">坐标的上下左右的情况：</span><span style="font-family:Tahoma;font-size:9pt;"></span>
<span style="font-family:宋体;font-size:9pt;"> 如果是</span><span style="font-family:Tahoma;font-size:9pt;">'B'</span><span style="font-family:宋体;font-size:9pt;">，则表示找到宝箱，输出并返回</span><span style="font-family:Tahoma;font-size:9pt;"></span>
<span style="font-family:宋体;font-size:9pt;"> 如果是空格，则表示尚未走到过，在地图上标记该位置，然后将坐标入队</span><span style="font-family:Tahoma;font-size:9pt;"></span>
<span style="font-family:Tahoma;font-size:9pt;">}</span>