Submission

Score: 0

User: letdown

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

Language: cpp

Time: 1.091 second

Submitted On: 2026-03-14 09:47:36

#include <bits/stdc++.h>

#define int long long
using namespace std;
signed main() {
    cin.tie(nullptr)->sync_with_stdio(0);
    int n, m;
    cin >> n >> m;

    int dirx[] = {0, 0, 1, -1, 1, -1, 1, -1};
    int diry[] = {1, -1, 0, 0, 1, -1, -1, 1};

    bool a[n][m];
    bool safe[n][m];
    memset(safe, 1, sizeof(safe));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];
            if (!a[i][j]) {
                safe[i][j] = 0;
                for (int k = 0; k < 8; k++) {
                    int chkn = i + dirx[k];
                    int chkm = j + diry[k];
                    if (chkn < 0 || chkm < 0 || chkn >= n || chkm >= m) continue;
                    safe[chkn][chkm] = 0;
                }
            }
        }
    }

    // for (auto &i : safe) {
    //     for (auto j : i) cout << j << " "; cout << "\n";
    // }

    int ans = LLONG_MAX;
    for (int i = 0; i < n; i++) {
        if (!safe[i][0]) continue;

        queue<pair<int, int>> q;
        q.push({i, 0});
        int dist[n][m];
        memset(dist, -1, sizeof(dist));
        dist[i][0] = 0;

        while (!q.empty()) {
            auto [curn, curm] = q.front();
            q.pop();

            for (int j = 0; j < 4; j++) {
                int newn = curn + dirx[j];
                int newm = curm + diry[j];

                if (newn < 0 || newm < 0 || newn >= n || newm >= m) continue;
                if (dist[newn][newm] != -1) continue;
                if (!safe[newn][newm]) continue;

                q.push({newn, newm});
                dist[newn][newm] = dist[curn][curm] + 1;

                if (newm == m-1) {
                    ans = min(ans, dist[newn][newm]+1);
                    break;
                }
            }
        }
    }
    if (ans == LLONG_MAX) ans = -1;
    cout << ans;
}