最短路径

#include <bits/stdc++.h>
using namespace std;

int main() {
    int m, n;
    cin >> m >> n;
    
    vector<vector<int>> grid(m, vector<int>(n));
    
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            cin >> grid[i][j];
        }
    }
    
    queue<pair<int, int>> q;
    
    // dist[i][j] 表示从起点到 (i, j) 的最短距离，-1 表示未访问过
    vector<vector<int>> dist(m, vector<int>(n, -1));
    
    q.push({0, 0});
    dist[0][0] = 0;
    
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};
    
    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        if (x == m - 1 && y == n - 1) {
            cout << dist[x][y] << endl;
            return 0;
        }
        
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            
            if (nx < 0 || ny < 0 || nx >= m || ny >= n 
                || grid[nx][ny] == 1 || dist[nx][ny] != -1) continue;
            
            dist[nx][ny] = dist[x][y] + 1;
            q.push({nx, ny});
        }
    }
    cout << -1 << endl;
    
    return 0;
}