2496 - 数据结构/栈和队列/迷宫寻宝
实验目的：
１、熟悉队列的实现和使用；
２、掌握一种路径搜索算法；
实验原理：
１、队列的原理：略
２、路径搜索算法的原理：利用队列记忆已经达到过，但还未展开搜索的地点，可以将所有地点无遗漏无重复的搜索到。
实验步骤：
１、定义坐标点类；
２、定义实现循环队列类，该类要求可以存储若干个坐标点。
３、利用队列实现路径搜索算法。
４、完成输入输出控制。
程欣宇 ２０１４年４月１３日编写
题目输入
输入由多个迷宫组成，每个迷宫开始一行是两个数字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.
提示
１、输入和地图存储结构提示，参考如下代码：
#define N 101 //最大行列数
char map[N][N];
int n,m;//行列数int main()<br />{
while(scanf("%d%d\n",&n,&m)==2)//能够读到两个数字说明还有输入要处理<br />{
for (int i=0;i<n;i++)<br />gets(map[i]);//读取第i行
map[0][1]='N';//封住出口 //TODO:已经拿到迷宫地形图，调用自己实现的迷宫寻宝算法<br />}
return 0;
}struct Point{2、坐标点结构体定义
int x,y;
Point(int x=0,int y=0){
this->x=x;
this->y=y;
}
};
3、支持任意元素类型的模板循环队列定义template<class T><br />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:自己实现}<br />bool isEmpty() {//TODO:自己实现 }
};4、利用坐标队列遍历迷宫可以达到的所有位置 把迷宫入口加入坐标队列while(队列非空){ 坐标 p=队列出队一个元素; 考察地图中p坐标的上下左右的情况：如果是'B'，则表示找到宝箱，输出并返回如果是空格，则表示尚未走到过，在地图上标记该位置，然后将坐标入队}
C语言解答
#include <stdio.h> #include <malloc.h> #define M 50 // 迷宫行数(包括外墙) #define N 50 // 迷宫列数(包括外墙) #define D 4 // 移动方向数 struct { int x,y; #if D==4 }move[D]={{0,1},{1,0},{0,-1},{-1,0}}; #endif // 元素类型 typedef struct { int x,y; // 当前点的行值，列值 int pre; // 前一点在队列中的序号 } QElemType; #define MAXQSIZE 251 // 最大队列长度(对于循环队列，最大队列长度要减1) typedef struct { QElemType *base;// 初始化的动态分配存储空间 相当于一个数组 int front; int rear; }SqQueue; //初始化队列为空 int InitQueue(SqQueue *Q) { Q->base=(QElemType *)malloc(MAXQSIZE*sizeof(QElemType)); if(!Q->base) return 0; Q->front=Q->rear=0; return 1; } // 判断队列是否为空 int QueueEmpty(SqQueue Q) { if(Q.front==Q.rear) return 1; else return 0; } // 入队 int EnQueue(SqQueue *Q,QElemType e) { if((Q->rear+1)%MAXQSIZE == Q->front) return (0);//队列满 Q->base[Q->rear] = e;//从队尾插入元素 Q->rear = (Q->rear+1) % MAXQSIZE; return 1; } // 出队 int DeQueue(SqQueue *Q,QElemType *e) { if(Q->front == Q->rear) return 0;// 队列空 *e=Q->base[Q->front]; Q->front=(Q->front+1)%MAXQSIZE; return 1; } // 广度搜索法求一条迷宫路径 int Path(char maze[M][N]) { SqQueue q; QElemType cur,next; // 当前点和下一点 int i,flag=1; // 当找到出口,flag=0 int x1, y1; // 终点的坐标 //当前点入口为（0,0）点 cur.x=0; cur.y=0; cur.pre = -1; // 设入口(第一点)的上一点的序号=-1 maze[cur.x][cur.y] = -1; // 初始点设为已访问过 InitQueue(&q); EnQueue(&q,cur); // 起点入队 while(!QueueEmpty(q)&&flag) { DeQueue(&q,&cur); // 出队qf为当前点 for(i=0;i<D;i++) // 向各个方向尝试 { // 下一点的坐标,正东起顺时针4个方向 next.x=cur.x+move[i].x; next.y=cur.y+move[i].y; if(maze[next.x][next.y] == ' ') { maze[next.x][next.y] = -1; // 已访问过 next.pre=q.front-1; EnQueue(&q,next); // 将下一点入队 } if(maze[next.x][next.y] == 'B') // 到达终点 { flag=0; x1=next.y; y1=next.x; break; } } } if(flag) // 搜索完整个队列还没到达终点 { printf("Box is not found.\n"); return 0; } else { printf("Box is found at x=%d y=%d.\n",x1,y1); return 1; } } int main() { int n,m; char map[M][N]; // 迷宫数组 while(scanf("%d%d\n",&n,&m)==2) //能够读到两个数字说明还有输入要处理 { for (int i=0;i<n;i++) gets(map[i]);//读取第i行 Path(map); } return 0; }
C++解答
#include "stdio.h" #define N 101 //最大行列数 char map[N][N]; int n,m;//行列数 struct Point{ int x,y; Point(int x=0,int y=0){ this->x=x; this->y=y; } }; template<class T> struct Queue{ T items[N*N]; int tail; //队尾指针 int front; //队首指针 Queue() { tail=0; front=0; } bool Push(T item) { int next=(tail+1)%(N*N); if (next==front) return false;//队满 items[tail]=item; tail=next; return true; } bool Pop(T &item) { if (front==tail) return false;//队空 item=items[front]; front=(front+1)%(N*N); return true; } bool isEmpty() { return front==tail; } }; bool test(Queue<Point> &points,int x,int y) { if (map[y][x]=='B') { printf("Box is found at x=%d y=%d.\n",x,y); return true; } if (map[y][x]==' ') { map[y][x]='G'; points.Push(Point(x,y)); } return false; } void mazz() { Queue<Point> points; map[0][1]='W'; points.Push(Point(1,1)); int k=0; while(points.isEmpty()==false&&k++<300) { Point p; points.Pop(p); if (map[p.y][p.x]=='B') { return; } if (test(points, p.x-1, p.y)) return; if (test(points, p.x+1, p.y)) return; if (test(points, p.x,p.y-1)) return; if (test(points, p.x,p.y+1))return; } printf("Box is not found.\n"); } /* 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 */ 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';//封住出口 mazz(); } return 0; }
提示
１、输入和地图存储结构提示，参考如下代码：
#define N 101 //最大行列数
char map[N][N];
int n,m;//行列数
int main()<br />
{
while(scanf("%d%d\n",&n,&m)==2)//能够读到两个数字说明还有输入要处理<br />
{
for (int i=0;i<n;i++)<br />
gets(map[i]);//读取第i行
map[0][1]='N';//封住出口
//TODO:已经拿到迷宫地形图，调用自己实现的迷宫寻宝算法<br />
}
return 0;
}
2、坐标点结构体定义
int x,y;
Point(int x=0,int y=0){
this->x=x;
this->y=y;
}
};
3、支持任意元素类型的模板循环队列定义
template<class T><br />
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:自己实现}<br />
bool isEmpty() {//TODO:自己实现 }
};
4、利用坐标队列遍历迷宫可以达到的所有位置
把迷宫入口加入坐标队列
while(队列非空)
{
坐标 p=队列出队一个元素;
考察地图中p坐标的上下左右的情况：
如果是'B'，则表示找到宝箱，输出并返回
如果是空格，则表示尚未走到过，在地图上标记该位置，然后将坐标入队
}