【Week2作业-A】Maze迷宫

算法

广度优先搜索（BFS）

题目描述

在一张5*5的地图上，0表示可以通过，1表示不能通过，要求找到一条坐上角到右下角的路径并输出；保证有且有唯一解。

解题思路

从左上角开始，使用BFS进行搜索，直到到达右下角。
在搜索到每个节点时，需要记录到达该节点的前一节点；最后从终点开始依次找到每个点的前一个节点，即为经过的路径，使用递归寻找并输出即可。

代码

#include<cstdio>
#include<iostream>
#include<queue>
using namespace std;
int m[10][10];
int d[10][10],pax[10][10],pay[10][10];
int bfs(){
    int dx[4]={1,-1,0,0};
    int dy[4]={0,0,1,-1};
    queue<int> qx,qy;
    qx.push(1);qy.push(1);
    m[1][1]=0;
    d[1][1]=0;
    int x,y;
    while(!qx.empty()){
        x=qx.front();y=qy.front();
        qx.pop();qy.pop();
        if(x==5&&y==5)
            break;
        for(int i=0;i<4;i++){
            int xx=x+dx[i];
            int yy=y+dy[i];
            if(m[xx][yy]==1){
                qx.push(xx);qy.push(yy);
                m[xx][yy]=0;
                d[xx][yy]=d[x][y]+1;
                pax[xx][yy]=x;pay[xx][yy]=y;
            }
        }
    }
    return d[5][5];
}
void find(int x,int y){
    if(x==1&&y==1){
        printf("(%d, %d)\n",x-1,y-1);
        return;
    }
    find(pax[x][y],pay[x][y]);
    printf("(%d, %d)\n",x-1,y-1);
    return;
}
int main(){
    int x;
    for(int i=1;i<=5;i++){
        for(int j=1;j<=5;j++){
            scanf("%d",&x);
            m[i][j]=1^x;
            //1为可通过，0为不可通过或已通过
            //已存在默认边界0
        }
    }
    int ans=bfs();
    find(5,5);
    return 0;
}

由于代码中没有使用结构体存储节点，导致代码中bfs()函数较为复杂；使用结构体将大大缩减代码长度。

题目总结

本题主要考察BFS的使用和BFS路径的记录。
时间复杂度为O(n²)，空间复杂度为O(n²)（n为地图行列数即5）；由于数据量很小，故不需要考虑时间及空间复杂度。