<h4>一、基本思路：</h4>
1.通过队列（数组，连续的地址）实现宽度优先搜索，以达到寻找最短路径的目的。
2.通过一个二维数组输出路线（以坐标的形式）。
<h4>二、代码解释：</h4>
//宽度优先搜索 迷宫
#include <stdio.h>
#define maxQueue 15
#define maxMazeRow 10
#define maxMazeCol 10
这个是一些头文件和其他信息：
1.maxQueue指的是队列数组的最大空间。
2.maxMazeRow和maxMazeCol指的是可输入迷宫的最大长度和宽度。
typedef struct adddress{
int row;
int col;
}Points;
定义一个结构体数组来记录坐标点，包括队列的数组也是以这个为结构的数组。
Points queue[maxQueue]={}; //define the queue
static int bot=0; //queue's bottom
static int top=0; //queue's top
void push(Points p) //push the queue
{
queue[top]=p;
top=(top+1)%maxQueue;
}
Points pop(void) //pop the queue
{
Points pi={0,0};
queue[bot]=pi;
bot=(bot+1)%maxQueue;
return queue[bot];
}
int is_empty() //judge the queue is(not) empty
{
return top==bot;
}
void print_queue() //print the queue
{
int i;
for(i=0;i<maxQueue;i++)
printf("(%d %d) ",queue[i].row,queue[i].col);
printf("\n");
}
以上代码是有关队列的一些内容，包括创建队列，也就是数组queue，还有top和bot分别指的是队列的头和尾，push、pop、is_empty分别是入队、出队、判断队列是否为空。
int arrow[][2]={{0,1},{1,0},{-1,0},{0,-1}}; //up,down,left,right(directions)
Points visited_last[maxMazeRow][maxMazeCol]={}; //store the line
arrow是待会需要往当前位置的四个方向搜索的那四个方向，具体的是向上、向右、向左、向下。
visited_last存储的是路线，举个例子，比如说当前走到（3，4），而这位置是从（2，4）走来的，那么在visited_last[3][4]储存的是一个坐标（2，4），这样的话待会就可以输出路线了。
void print_maze(int maxRow,int maxCol,int *maze)
{
int i,j;
for(i=0;i<maxRow;i++){
for(j=0;j<maxCol;j++)
printf("%d ",*((maze+i*maxMazeCol)+j));
printf("\n");
}
printf("\n");
}
void print_road(Points p)
{
if(p.col==0&&p.row==0)
return ;
else if(p.col!=0||p.row!=0)
{
p = visited_last[p.row][p.col];
print_road(p);
printf("(%d, %d)\n", p.row, p.col);
}
}
这两个分别是输出迷宫的图和输出路线，因为我们用visited_last是倒过来回去输出的，也就是说坐标是从终点往起点输出的，所以我们需要用递归使他反过来从起点输出到终点。
int main()
{
int maze[maxMazeRow][maxMazeCol]={};
int maxCol,maxRow;
printf("input the maze's row and col:\n");
scanf("%d %d",&maxRow,&maxCol);
printf("input the maze:\n");
if(maxCol>10||maxRow>10){
printf("the max row and col are all 10!");
}else{
int i,j;
for(i=0;i<maxRow;i++){
for(j=0;j<maxCol;j++){
scanf("%d",&maze[i][j]);
}
}
printf("\n");
//input the maze
Points p={0,0};
push(p);
maze[0][0]=2;
int k;
while(!is_empty()){
if(p.row==maxRow-1&&p.col==maxCol-1)
break;
for(k=0;k<4;k++){
if((p.row+arrow[k][0]<maxRow&&p.col+arrow[k][1]<maxCol)&&p.row+arrow[k][0]>=0&&
p.col+arrow[k][1]>=0&&maze[p.row+arrow[k][0]][p.col+arrow[k][1]]==0){
maze[p.row+arrow[k][0]][p.col+arrow[k][1]]=2;
visited_last[p.row+arrow[k][0]][p.col+arrow[k][1]]=p;
Points visitpoint={p.row+arrow[k][0],p.col+arrow[k][1]};
push(visitpoint);
//search the maze's point , mark the path.
}
}
p=pop();
}
if (p.row == maxRow - 1 && p.col == maxCol - 1) //print the line
{
print_road(p);
printf("(%d, %d)\n", p.row, p.col);//print the path
}else
printf("No path!\n");
}
return 0;
}
主函数功能主要看里面的备注即可。
<h4>三、总结</h4>
本次作业与上周类似，只不过使用了宽度优先搜索（广度优先搜索），用广度优先搜索的好处就是能够最先找到最短路径，而深度优先搜索他是一条路径搜到底不通才倒过来继续搜索下一条路径，也就是说最先搜索到终点的那条路径就是出路，至于哪条路是取决于你的搜索方向的先后顺序。
总的来说，这两种搜索方式有类比之处，但也有不同之处，若用树状图理解的话，相信会很好理解的。
<h4>附：完整代码</h4>
//宽度优先搜索 迷宫
#include <stdio.h>
#define maxQueue 15
#define maxMazeRow 10
#define maxMazeCol 10
#define bool _Bool
typedef struct adddress{
int row;
int col;
}Points;
Points queue[maxQueue]={}; //define the queue
static int bot=0; //queue's bottom
static int top=0; //queue's top
void push(Points p) //push the queue
{
queue[top]=p;
top=(top+1)%maxQueue;
}
Points pop(void) //pop the queue
{
Points pi={0,0};
queue[bot]=pi;
bot=(bot+1)%maxQueue;
return queue[bot];
}
int is_empty() //judge the queue is(not) empty
{
return top==bot;
}
void print_queue() //print the queue
{
int i;
for(i=0;i<maxQueue;i++)
printf("(%d %d) ",queue[i].row,queue[i].col);
printf("\n");
}
int arrow[][2]={{0,1},{1,0},{-1,0},{0,-1}}; //up,down,left,right(directions)
Points visited_last[maxMazeRow][maxMazeCol]={}; //store the line
void print_maze(int maxRow,int maxCol,int *maze)
{
int i,j;
for(i=0;i<maxRow;i++){
for(j=0;j<maxCol;j++)
printf("%d ",*((maze+i*maxMazeCol)+j));
printf("\n");
}
printf("\n");
}
void print_road(Points p)
{
if(p.col==0&&p.row==0)
return ;
else if(p.col!=0||p.row!=0)
{
p = visited_last[p.row][p.col];
print_road(p);
printf("(%d, %d)\n", p.row, p.col);
}
}
int main()
{
int maze[maxMazeRow][maxMazeCol]={};
int maxCol,maxRow;
printf("input the maze's row (max 10) and col (max 10):\n");
scanf("%d %d",&maxRow,&maxCol);
printf("input the maze:\n");
if(maxCol>10||maxRow>10){
printf("the max row and col are all 10!");
}else{
int i,j;
for(i=0;i<maxRow;i++){
for(j=0;j<maxCol;j++){
scanf("%d",&maze[i][j]);
}
}
printf("\n");
Points p={0,0};
push(p);
maze[0][0]=2;
int k;
while(!is_empty()){
if(p.row==maxRow-1&&p.col==maxCol-1)
break;
for(k=0;k<4;k++){
if((p.row+arrow[k][0]<maxRow&&p.col+arrow[k][1]<maxCol)&&p.row+arrow[k][0]>=0&&
p.col+arrow[k][1]>=0&&maze[p.row+arrow[k][0]][p.col+arrow[k][1]]==0){
maze[p.row+arrow[k][0]][p.col+arrow[k][1]]=2;
visited_last[p.row+arrow[k][0]][p.col+arrow[k][1]]=p;
Points visitpoint={p.row+arrow[k][0],p.col+arrow[k][1]};
push(visitpoint);
}
}
print_queue();
p=pop();
print_maze(maxRow,maxCol,maze); //print the maze
}
if (p.row == maxRow - 1 && p.col == maxCol - 1) //print the line
{
print_road(p);
printf("(%d, %d)\n", p.row, p.col);
}else
printf("No path!\n");
}
return 0;
}
网友评论