题解 | 迷宫寻路

// 经典迷宫
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<string> grid(n);
    for (int i = 0; i < n; ++i) cin >> grid[i];

    if (grid[0][0] == '#' || grid[n - 1][m - 1] == '#') {
        cout << "No\n";
        return 0;
    }
    // 构造数组
    vector<vector<int>> visited(n, vector<int>(m, 0));
    queue<pair<int, int>> q;
    q.push(make_pair(0, 0));
    visited[0][0] = 1;
    const int dx[4] = {1, -1, 0, 0};
    const int dy[4] = {0, 0, 1, -1};

    while (!q.empty()) {
        pair<int, int> cur = q.front();
        q.pop();
        int x = cur.first, y = cur.second;
        if (x == n - 1 && y == m - 1) {
            cout << "Yes\n";
            return 0;
        }
        for (int dir = 0; dir < 4; ++dir) {
            int nx = x + dx[dir];
            int ny = y + dy[dir];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if (grid[nx][ny] == '#') continue;
            if (visited[nx][ny]) continue;
            visited[nx][ny] = 1;
            q.push(make_pair(nx, ny));
        }
    }

    cout << "No\n";
    return 0;
}