走出迷宫

解题思路

迷宫是一个 的矩阵。起点在地图中用“S”来表示，终点用“E”来表示，障碍物用“#”来表示，空地用“.”来表示。障碍物不能通过。
求能否从起点走到终点。

本题可以使用 BFS算法，使用队列 que 实现。
d 表示可以移动的 4 个方向，visited 表示已遍历过的点。

C++代码

#include<iostream>
#include<vector>
#include<queue>
using namespace std;

int N, M;
int d[4][2] = {{1,0}, {-1,0}, {0,1}, {0,-1}};

bool isReach(vector<vector<char>>& ground, int sx, int sy){
    vector<vector<bool>> visited(N, vector<bool>(M, false));
    visited[sx][sy] = true;
    queue<pair<int,int>> que;
    que.push(make_pair(sx, sy));
    while(!que.empty()){
        int x = que.front().first;
        int y = que.front().second;
        for(int i=0; i<4; ++i){
            int tx = x + d[i][0];
            int ty = y + d[i][1];
            if(tx >= 0 && tx < N && ty >= 0 && ty < M){
                if(ground[tx][ty] == '.' && visited[tx][ty] == false){
                    visited[tx][ty] = true;
                    que.push(make_pair(tx, ty));
                }
                if(ground[tx][ty] == 'E')
                    return true;
            }
        }
        que.pop();
    }
    return false;
}

int main(){
    while(cin >> N >> M){
        vector<vector<char>> ground(N, vector<char>(M));
        int sx, sy;
        for(int i=0; i<N; ++i){
            for(int j=0; j<M; ++j){
                cin >> ground[i][j];
                if(ground[i][j] == 'S'){
                    sx = i;
                    sy = j;
                }
            }
        }
        if(isReach(ground, sx, sy))
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    }
    return 0;
}