题解 | 迷宫寻路

#include <iostream>
#include <vector>
using namespace std;
struct Pt {
    int y;
    int x;
};
int main() {
    int n, m;
    cin >> n >> m;
    vector<string> map(n);
    for(auto& row : map) {
        cin >> row;
    }
    vector<vector<bool>> visited(n,vector<bool>(m));
    vector<vector<int>> step(n,vector<int>(m));
    vector<Pt> stack;
    stack.push_back(Pt{0,0});
    vector<Pt> round = {
        {-1,0}, {1,0}, {0,-1},{0,1}
    };
    while(stack.size()) {
        auto pt = stack.back();
        stack.pop_back();
        if(visited[pt.y][pt.x]) {
            continue;
        }
        visited[pt.y][pt.x] = true;
        // 如果只有一个格子，则不会进入round中
        // 此处可以正确判断
        if(pt.y == n-1 && pt.x == m-1) {
            cout << "Yes" << endl;
            return 0;
        }
        for(auto& v : round) {
            int y = pt.y + v.y;
            int x = pt.x + v.x;
            if( x < 0 || y < 0 || x >= m || y >=n) {
                continue;
            }
            if(visited[y][x]) {
                continue;
            }
            if(map[y][x] == '#') {
                continue;
            }
            stack.push_back(Pt{y,x});
        }
    }
    cout << "No" << endl;
}
// 64 位输出请用 printf("%lld")