题解 | 走迷宫

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,-1,1 };
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<vector<char>> a(n+1, vector<char>(m+1));
    vector<vector<int>> b(n+1, vector<int>(m+1,-1));
    
    int xs, ys, xt, yt;
    cin >> xs >> ys >> xt >> yt;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
    }
    int f = false;
    queue<pair<int, int>> q;
    q.push({ xs,ys });
    b[xs][ys] = 0;
    //int x = xs, y = ys;
    while (!q.empty()) {
        auto temp = q.front();
        q.pop();
        int x = temp.first;//队头
        int y = temp.second;
        if (x == xt && y == yt) {
            f = true;
            break;
        }
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx<1 || nx>n || ny<1 || ny>m)continue;
            if (a[nx][ny] != '*' && b[nx][ny] == -1) {
                b[nx][ny] = b[x][y] + 1;
                q.push({ nx,ny });
            }
        }
    }
    if (f)cout << b[xt][yt] << endl;
    else cout << "-1" << endl;

}

背