<h4>一、基本思路：</h4>
1.通過隊(duì)列（數(shù)組，連續(xù)的地址）實(shí)現(xiàn)寬度優(yōu)先搜索，以達(dá)到尋找最短路徑的目的。
2.通過一個二維數(shù)組輸出路線（以坐標(biāo)的形式）。
<h4>二、代碼解釋：</h4>
//寬度優(yōu)先搜索 迷宮
#include <stdio.h>
#define maxQueue 15
#define maxMazeRow 10
#define maxMazeCol 10
這個是一些頭文件和其他信息：
1.maxQueue指的是隊(duì)列數(shù)組的最大空間。
2.maxMazeRow和maxMazeCol指的是可輸入迷宮的最大長度和寬度。
typedef struct adddress{
int row;
int col;
}Points;
定義一個結(jié)構(gòu)體數(shù)組來記錄坐標(biāo)點(diǎn)，包括隊(duì)列的數(shù)組也是以這個為結(jié)構(gòu)的數(shù)組。
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");
}
以上代碼是有關(guān)隊(duì)列的一些內(nèi)容，包括創(chuàng)建隊(duì)列，也就是數(shù)組queue，還有top和bot分別指的是隊(duì)列的頭和尾，push、pop、is_empty分別是入隊(duì)、出隊(duì)、判斷隊(duì)列是否為空。
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是待會需要往當(dāng)前位置的四個方向搜索的那四個方向，具體的是向上、向右、向左、向下。
visited_last存儲的是路線，舉個例子，比如說當(dāng)前走到（3，4），而這位置是從（2，4）走來的，那么在visited_last[3][4]儲存的是一個坐標(biāo)（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);
}
}
這兩個分別是輸出迷宮的圖和輸出路線，因?yàn)槲覀冇胿isited_last是倒過來回去輸出的，也就是說坐標(biāo)是從終點(diǎn)往起點(diǎn)輸出的，所以我們需要用遞歸使他反過來從起點(diǎn)輸出到終點(diǎn)。
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;
}
主函數(shù)功能主要看里面的備注即可。
<h4>三、總結(jié)</h4>
本次作業(yè)與上周類似，只不過使用了寬度優(yōu)先搜索（廣度優(yōu)先搜索），用廣度優(yōu)先搜索的好處就是能夠最先找到最短路徑，而深度優(yōu)先搜索他是一條路徑搜到底不通才倒過來繼續(xù)搜索下一條路徑，也就是說最先搜索到終點(diǎn)的那條路徑就是出路，至于哪條路是取決于你的搜索方向的先后順序。
總的來說，這兩種搜索方式有類比之處，但也有不同之處，若用樹狀圖理解的話，相信會很好理解的。
<h4>附：完整代碼</h4>
//寬度優(yōu)先搜索 迷宮
#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;
}
