题意：
        给定一个迷宫，问从左上角到右下角的最短路线。（要输出路径）




方法一：
bfs
思路：
        利用层次遍历（bfs）寻找最短路径。
        fa[ ][ ]表示当前坐标的父亲坐标。
        将起点(0,0)加入队列，四个方向遍历相邻坐标，如果相邻坐标未访问过并且可以走，则入队列，
        并且将当前坐标指定父亲坐标。

        以此类推，找到终点(n-1,m-1)。
        再通过递归输出最短路径的线路。
    

#include <bits/stdc++.h>

using namespace std;
int a[15][15],vis[15][15];
int b[4][2]={{-1,0},{0,1},{1,0},{0,-1}};//上下左右四个方向
pair<int,int> fa[15][15];//记录当前下标的父亲下标

void dfs(int x,int y){//dfs打印路径
    if(x==0&&y==0)//如果到达左上角，则退出
        return;
    auto t=fa[x][y];
    dfs(t.first,t.second);
    printf("(%d,%d)\n",x,y);
}
int main(){

    int n,m;
    while(cin >> n >> m){
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                cin >> a[i][j];//输入迷宫
        memset(vis,0,sizeof(vis));
        memset(fa,0,sizeof(fa));
        queue<pair<int,int>> q;//队列
        q.push({0,0});//左上角坐标入队列
        vis[0][0]=1;
        while(!q.empty()){
            auto u=q.front();
            q.pop();
            if(u.first==n-1&&u.second==m-1){
                break;
            }
            for(int i=0;i<4;i++){//遍历四个方向
                int nx=u.first+b[i][0],ny=u.second+b[i][1];
                if(nx<0||nx>=n||ny<0||ny>=m)
                    continue;
                if(vis[nx][ny]==0&&a[nx][ny]==0){//如果当前坐标未访问过并且可以走，则入队列，并且当前坐标指定父亲坐标
                    fa[nx][ny]={u.first,u.second};
                    q.push({nx,ny});
                    vis[nx][ny]=1;
                }
            }
        }
        printf("(%d,%d)\n",0,0);
        dfs(n-1,m-1);
    }
    return 0;
}


时间复杂度：
空间复杂度：

方法二：
dfs

思路：
       深度优先搜索，利用二维数组记录起点到当前点的最短距离。
        向四个方向（上下左右）dfs，维护最短距离，。
        最后逆向输出最短路径。
#include <bits/stdc++.h>

using namespace std;
int a[15][15],vis[15][15];
int b[4][2]={{-1,0},{0,1},{1,0},{0,-1}};//上下左右四个方向
pair<int,int> fa[15][15];//记录当前下标的父亲下标
int dis[15][15];//记录起点到当前点的最短距离
int n,m;

void f(int x,int y){//dfs打印路径
    if(x==0&&y==0)//如果到达左上角，则退出
        return;
    auto t=fa[x][y];
    f(t.first,t.second);
    printf("(%d,%d)\n",x,y);
}
void dfs(int x,int y){
    for(int i=0;i<4;i++){//遍历四个方向
        int nx=x+b[i][0],ny=y+b[i][1];
        if(nx<0||nx>=n||ny<0||ny>=m)
            continue;
        if(a[nx][ny]==0&&vis[nx][ny]==0&&dis[nx][ny]>dis[x][y]+1){//如果当前坐标可走，并且没访问过，并且距离短，则访问该坐标
            vis[nx][ny]=1;//设置为已访问
            dis[nx][ny]=dis[x][y]+1;//更新最短距离
            fa[nx][ny]={x,y};//设置父亲坐标
            dfs(nx,ny);
            vis[nx][ny]=0;//还原
        }
    }
}
int main(){

    while(cin >> n >> m){
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                cin >> a[i][j];//输入迷宫
        memset(dis,0x3f,sizeof(dis));
        memset(vis,0,sizeof(vis));
        memset(fa,0,sizeof(fa));
        vis[0][0]=1;
        dis[0][0]=0;
        dfs(0,0);
        printf("(%d,%d)\n",0,0);
        f(n-1,m-1);
    }
    return 0;
}



时间复杂度：
空间复杂度：