Submission

Score: 100

User: kittipos

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

Language: cpp

Time: 0.113 second

Submitted On: 2026-03-09 13:54:49

#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] == 2) continue;
            for (int j = -1; j <= 1; j++) {
                for (int k = -1; k <= 1; k++) {
                    int nx = max(0, min(w-1, x+j));
                    int ny = max(0, min(h-1, y+k));
                    if (space[ny][nx] == 0) goto conti;
                }
            }
            goto notconti;
            conti:
                continue;
            notconti:

            // cout << "check point" << endl;

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

            space[y][x] = 2;

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

    cout << -1;

    return 0;
}