Submission

Score: 0

User: letdown

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

Language: cpp

Time: 1.091 second

Submitted On: 2026-03-13 23:44:41

#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;

    bool a[n][m];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];
        }
    }

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

    int ans = LLONG_MAX;
    for (int i = 0; i < n; i++) {
        if (!a[i][0]) continue;
        bool invalid = 0;
        for (int k = 0; k < 8; k++) {
            int chkn = i + dirx[k];
            int chkm = diry[k];
            if (chkn < 0 || chkm < 0 || chkn >= n || chkm >= m) continue;
            if (!a[chkn][chkm]) invalid = 1;
        }
        if (invalid) continue;

        int vis[n][m];
        memset(vis, 0, sizeof(vis));
        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();

            if (curm == m-1) {
                ans = min(ans, dist[curn][curm]+1);
                break;
            }

            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 (vis[newn][newm]) continue;
                if (!a[newn][newm]) continue;

                bool invalid = 0;
                for (int k = 0; k < 8; k++) {
                    int chkn = newn + dirx[k];
                    int chkm = newm + diry[k];
                    if (chkn < 0 || chkm < 0 || chkn >= n || chkm >= m) continue;
                    if (!a[chkn][chkm]) invalid = 1;
                }
                if (invalid) continue;

                vis[newn][newm] = 1;
                q.push({newn, newm});
                dist[newn][newm] = dist[curn][curm] + 1;
            }
        }
    }
    if (ans == LLONG_MAX) ans = -1;
    cout << ans;
}