题意

在一个迷宫中，只能上下左右走，找出从左上角到右下角的路线。

解答：DFS

对于迷宫类题目，由于题目保证了有且只有一条通道，因此我们可以用深度优先搜索（DFS）解决这个问题。

#include<bits/stdc++.h>
using namespace std;
int mp[11][11],used[11][11];//mp数组存储地图，used数组存储当前该位置是否已经走过
int n,m;
const int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};//dx和dy分别代表上下左右方向
int isValid(int posx,int posy)
{
    if(posx>=0&&posx<n&&posy>=0&&posy<m&&!used[posx][posy]&&!mp[posx][posy]) return 1;
    return 0;
}//判断当前位置是否合法，（1）必须在迷宫范围内，（2）当前位置不能是墙壁，（3）当前位置不能走过
bool flag=true;
void dfs(int x,int y)
{
    if(!flag) return;//已经输出了路径，不再搜索
    //printf("%d %d\n",x,y);
    if(x==n-1&&y==m-1)//已到达终点就输出路径
    {
        int i=0,j=0;
        do
        {
            cout << '(' << i <<',' << j <<')' << endl;
            used[i][j]=0;
            if(used[i][j+1]) j++;
            else if(used[i+1][j])i++;
            else if(used[i-1][j])i--;
            else if(used[i][j-1])j--;
        }
        while(!(i==n-1&&j==m-1));//只要没到终点就继续输出
        cout << '(' << n-1 <<',' << m-1 <<')' << endl;//输出终点
        flag=false;
    }
    else
    for(int i=0;i<=3;i++)
    {
        if(isValid(x+dx[i],y+dy[i]))//若下一步是合法的
        {used[x+dx[i]][y+dy[i]]=1;dfs(x+dx[i],y+dy[i]);used[x+dx[i]][y+dy[i]]=0;}//搜索下一步的路径
    }
}
int main()
{
        
    while(~scanf("%d%d",&n,&m))//输入地图规模
    {
        flag=true;
        memset(used,0,sizeof used);
        for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
        scanf("%d",&mp[i][j]);//读入地图
        used[0][0]=1;
        dfs(0,0);
    }
}

时间复杂度：$O(nm)O(nm)$,dfs最多可以遍历整个地图。

空间复杂度：$O(nm)O(nm)$,存储地图和判断位置是否走过使用的数组的空间。

解答：BFS

除此之外，我们还可以用广度优先搜索（BFS）解决这个问题。

#include<bits/stdc++.h>
using namespace std;
struct POS
{
int x,y;
};
int mp[11][11],used[11][11];//mp数组存储地图，used数组存储当前该位置是否已经走过
int n,m;
const int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};//dx和dy分别代表上下左右方向
int isValid(int posx,int posy)
{
    if(posx>=0&&posx<n&&posy>=0&&posy<m&&!used[posx][posy]&&!mp[posx][posy]) return 1;
    return 0;
}//判断当前位置是否合法，（1）必须在迷宫范围内，（2）当前位置不能是墙壁，（3）当前位置不能走过
bool flag=true;
void bfs()
{
    queue<vector<POS> > T;
    POS tmp;tmp.x=tmp.y=0;
    T.push(vector<POS>{tmp});
	while(!T.empty())
    {
    vector <POS> t=T.front();
    T.pop();
    tmp=t[t.size()-1];
    if(tmp.x==n-1&&tmp.y==m-1)
    {
  		for(int i=0;i<t.size();++i)
        {
        cout << '(' <<t[i].x << ',' << t[i].y <<')'<<endl;
        }
        return;
    }
    	for(int i=0;i<4;i++)
        {
        if(isValid(tmp.x+dx[i],tmp.y+dy[i])) {POS a;a.x=tmp.x+dx[i];a.y=tmp.y+dy[i];t.push_back(a);T.push(t);used[a.x][a.y]=true;t.pop_back();}
        }
    }
}
int main()
{
        
    while(~scanf("%d%d",&n,&m))//输入地图规模
    {
        flag=true;
        memset(used,0,sizeof used);
        for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
        scanf("%d",&mp[i][j]);//读入地图
        used[0][0]=1;
        bfs();
    }
}

时间复杂度：$O(nm)O(nm)$,bfs最多可以遍历整个地图。

空间复杂度：$O(nm)O(nm)$,存储地图和判断位置是否走过使用的数组的空间。

蓝色为BFS路径，红色为DFS路径