問題: 迷路の最短経路 (C++)

迷路の最短経路 (C++)

問題

h 行 w 列の迷路を入力として受け取り、幅優先探索（BFS）で左上から右下までの最短手数を求めてください。'.' は通路、'#' は壁で、上下左右に1マスずつ移動できます。到達できない場合は「ゴールに到達できません」と表示します。

入力例

4 5
..#..
.#...
...#.
#....

出力例

最短手数: 7

参照コード

コピーはできません。自分でタイピングしてください。

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

int main() {
    int h, w;
    cin >> h >> w;
    vector<string> grid(h);
    for (int i = 0; i < h; i++) {
        cin >> grid[i];
    }
    vector<vector<int>> dist(h, vector<int>(w, -1));
    queue<pair<int, int>> q;
    dist[0][0] = 0;
    q.push({0, 0});
    int dy[] = {-1, 1, 0, 0};
    int dx[] = {0, 0, -1, 1};
    while (!q.empty()) {
        auto [y, x] = q.front();
        q.pop();
        for (int d = 0; d < 4; d++) {
            int ny = y + dy[d], nx = x + dx[d];
            if (ny < 0 || ny >= h || nx < 0 || nx >= w) continue;
            if (grid[ny][nx] == '#' || dist[ny][nx] != -1) continue;
            dist[ny][nx] = dist[y][x] + 1;
            q.push({ny, nx});
        }
    }
    if (dist[h - 1][w - 1] >= 0) {
        cout << "最短手数: " << dist[h - 1][w - 1] << endl;
    } else {
        cout << "ゴールに到達できません" << endl;
    }
    return 0;
}

迷路の最短経路 (C++)

問題

入力例

出力例

参照コード

入力エリア