Submission

Score: 100

User: poni

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

Language: cpp

Time: 0.061 second

Submitted On: 2026-10-08 20:03:25

#include <bits/stdc++.h>

using namespace std;
#define int long long

#define pii pair<int, int>
#define vi vector<int>

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    int n, m;
    cin >> n >> m;

    queue<pii> q;

    int dir4[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    int dir8[8][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, -1}, {-1, 1}, {1, 1}, {-1, -1}};

    bool ori[n][m];
    bool a[n][m];
    for (auto &i : ori) for (auto &j : i) cin >> j;
    for (auto &i : a) for (auto &j : i) j = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (ori[i][j]) continue;
            a[i][j] = 0;
            for (auto [di, dj] : dir8) {
                int ni = i+di, nj = j+dj;
                if (ni<0 || nj<0 || ni>=n || nj>= m) continue;
                a[ni][nj] = 0;
            }
        }
    }

    vector<vi> dist(n, vi(m, LLONG_MAX));
    for (int i = 0; i < n; i++) {
        if (a[i][0]) {
            q.emplace(i, 0);
            dist[i][0] = 1;
        }
    }

    while (!q.empty()) {
        auto [ci, cj] = q.front();
        q.pop();
        for (auto [di, dj] : dir4) {
            int ni = ci+di, nj = cj+dj;
            if (ni<0 || nj<0 || ni>=n || nj>= m) continue;  
            if (!a[ni][nj] || dist[ni][nj] != LLONG_MAX) continue;
            dist[ni][nj] = dist[ci][cj] + 1;
            q.emplace(ni, nj);
        }
    }

    int ans = LLONG_MAX;
    for (int i = 0; i < n; i++) ans = min(ans, dist[i][m-1]);
    if (ans == LLONG_MAX) ans = -1;
    cout << ans << "\n";
}