Submission

Score: 100

User: KantaponZ

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

Language: cpp

Time: 0.079 second

Submitted On: 2025-12-07 13:55:29

#include <bits/stdc++.h>
using namespace std;

int N, M;
int dist[1005][1005];
bool vis[1005][1005];
queue<pair<int,int>> q;

int xx[] = {-1, 0, 1, 0};
int yy[] = {0, -1, 0, 1};

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    cin >> N >> M;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            int x; cin >> x;
            if (x == 0) {
                vis[i - 1][j - 1] = vis[i][j - 1] = vis[i + 1][j - 1] = 1;
                vis[i - 1][j] = vis[i][j] = vis[i + 1][j] = 1;
                vis[i - 1][j + 1] = vis[i][j + 1] = vis[i + 1][j + 1] = 1;
            }
            dist[i][j] = 1e9;
        }
        q.emplace(i, 1);
        if (!vis[i][1]) dist[i][1] = 1;
    }

    while (!q.empty()) {
        auto [y, x] = q.front();
        q.pop();
        if (vis[y][x]) continue;
        vis[y][x] = 1;
        for (int i = 0; i < 4; i++) {
            int nx = x + xx[i], ny = y + yy[i];
            if (nx < 1 || nx > M) continue;
            if (ny < 1 || ny > N) continue;
            if (vis[ny][nx]) continue;
            q.emplace(ny, nx);
            dist[ny][nx] = min(dist[ny][nx], dist[y][x] + 1);
        }
    }

    int ans = INT_MAX;
    for (int i = 1; i <= N; i++) {
        if (dist[i][M] == 1e9) continue;
        ans = min(dist[i][M], ans);
    }

    /*for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            cout << dist[i][j] << " ";
        } cout << endl;
    }*/

    if (ans == INT_MAX) cout << -1;
    else cout << ans;

}