本文共 2431 字，大约阅读时间需要 8 分钟。

走出迷宫

链接：https://ac.nowcoder.com/acm/problem/14572

来源：牛客网

题目描述

小明现在在玩一个游戏，游戏来到了教学关卡，迷宫是一个N*M的矩阵。 小明的起点在地图中用“S”来表示，终点用“E”来表示，障碍物用“#”来表示，空地用“.”来表示。 障碍物不能通过。小明如果现在在点（x，y）处，那么下一步只能走到相邻的四个格子中的某一个：（x+1，y），（x-1，y），（x，y+1），（x，y-1）； 小明想要知道，现在他能否从起点走到终点。 输入描述: 本题包含多组数据。 每组数据先输入两个数字N,M 接下来N行，每行M个字符，表示地图的状态。 数据范围： 2<=N,M<=500 保证有一个起点S，同时保证有一个终点E. 输出描述: 每组数据输出一行，如果小明能够从起点走到终点，那么输出Yes，否则输出No 示例1 输入 复制 3 3 S… …E … 3 3 S##

##E

输出 复制 Yes No

#include
   
    using namespace std;typedef long long ll;char g[502][502];bool vis[502][502];int X[4]={   0,1,0,-1};int Y[4]={   1,0,-1,0};int sx,sy,dx,dy;int n,m;bool flag ;bool check(int x,int y){       if(g[x][y]=='#'||vis[x][y]) return false;    if(x<1||x>n||y<1||y>m) return false;    return true;}void dfs(int x,int y){       if(x==dx&&y==dy) {   flag = true;return;}//退出搜索    for(int i=0;i<4;i++)    {           int newx = x+X[i];        int newy = y+Y[i];        if(check(newx,newy))        {               vis[newx][newy] = true;            dfs(newx,newy);            //vis[newx][newy] = false;            //加上回溯会超时，不能加，因为回溯复杂度为n！        }    }}void bfs(int x,int y){       queue
    
     
       >q;    q.push(make_pair(x,y));    while(!q.empty())    {           int xx = q.front().first;        int yy = q.front().second;        q.pop();        if(xx==dx&&yy==dy)        {               flag=true;            return ;        }        for(int i=0;i<4;i++)        {               int newx = xx + X[i];            int newy = yy + Y[i];            if(check(newx,newy))            {                   vis[newx][newy] = true;                q.push(make_pair(newx,newy));                            }        }    }}void solve(){       for(int i=1;i<=n;i++)    {           for(int j=1;j<=m;j++)        {               cin>>g[i][j];            if(g[i][j]=='S') sx=i,sy=j;            if(g[i][j]=='E') dx=i,dy=j;        }    }    dfs(sx,sy);    //bfs(sx,sy);    if(flag) cout<<"Yes\n";    else cout<<"No\n";}int main(){       ios::sync_with_stdio(false);    cin.tie(0),cout.tie(0);    while(cin>>n>>m)    {           memset(vis,false,sizeof(vis));//多组样例重置数组很重要        flag = false;        solve();    }    return 0;}/*10 10S.........#########............#########...........########..########..########..########..........E*/
     
    
   

本题可以采用dfs或者bfs的方法

dfs：

加上回溯复杂度更高，为 n！，所以回溯算法会超时。

思路：

每次的遍历都面临最多四种选择，进行搜索遍历。

未遍历过，且不是障碍，就可以进行标记遍历。

当遍历的坐标等于终点的坐标时，就退出。

bfs：

到达终点再标记，不到达终点就一直进行到底。

---

如要领取更多资料，关注公众号回复关键字领取。