Submission

Score: 0

User: kittipos

Problemset: ย่องเบาหลบกับระเบิด

Language: cpp

Time: 0.461 second

Submitted On: 2026-03-09 13:48:18

#include <bits/stdc++.h>

using namespace std;


int main() {
    int h, w;
    cin >> h >> w;

    vector<vector<int>> space;
    space.assign(h, vector<int>(w));
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            cin >> space[i][j];
        }
    }

    // multisource multidestination bfs
    queue<pair<int, int>> q;
    // push all source to q
    for (int i = 0; i < h; i++) {
        q.push({0, i});
    }

    int cnt = 0;
    while (!q.empty()) {
        int chuck = q.size();
        cnt++;
        for (int i = 0; i < chuck; i++) {
            pair<int, int> cur = q.front();
            q.pop();

            int x = cur.first;
            int y = cur.second;

            if (x < 0 || y < 0 || x >= w || y >= h) continue;
            if (
                space[y][x] == 0 ||
                space[min(y+1, h-1)][x] == 0 ||
                space[max(0, y-1)][x] == 0 ||
                space[y][min(x+1, w-1)] == 0 ||
                space[y][max(0, x-1)] == 0 // anotheer condition may needed
            ) continue;
            // cout << "check point" << endl;

            if (x+1 == w) {
                cout << cnt;
                return 0;
            }

            q.push({x+1, y});
            q.push({x-1, y});
            q.push({x, y+1});
            q.push({x, y-1});
        }
    }

    cout << -1;

    return 0;
}