提出 #73588680

---

ソースコード 拡げる

#include <iostream>
#include <vector>
#include <deque>
#include <string>
#include <tuple>
using namespace std;

const int INF = 1e9;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

int main() {
    int N, M;
    cin >> N >> M;
    vector<string> grid(N);
    for (int i = 0; i < N; i++) {
        cin >> grid[i];
    }

    // dist数组，初始化为无穷大
    vector<vector<int>> dist(N, vector<int>(M, INF));
    dist[0][0] = 0; // 起点

    deque<pair<int, int>> dq;
    dq.push_front({0, 0});

    while (!dq.empty()) {
        auto [x, y] = dq.front();
        dq.pop_front();

        // 如果已经到达终点，可以提前退出（但为了保险，继续直到队列空也可以）
        // if (x == N-1 && y == M-1) break;

        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;

            int cost = (grid[nx][ny] == '#' ? 1 : 0);
            int new_dist = dist[x][y] + cost;

            if (new_dist < dist[nx][ny]) {
                dist[nx][ny] = new_dist;
                if (cost == 0) {
                    // 如果是通道，代价为0，加入队列前端优先处理
                    dq.push_front({nx, ny});
                } else {
                    // 如果是墙，代价为1，加入队列后端
                    dq.push_back({nx, ny});
                }
            }
        }
    }

    cout << dist[N-1][M-1] << endl;

    return 0;
}

提出情報

ジャッジ結果