Submission

Score: 100

User: SnowAveNode

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

Language: cpp

Time: 0.055 second

Submitted On: 2026-04-11 19:23:04

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

const int nx = 1e5 + 5, MOD = 1e9 + 7, inf = 2e9; const ll INF = 4e18;
int dy[] = {-1, 1, 0, 0}, dx[] = {0, 0, -1, 1};
int dyb[] = {-1, 1, 0, 0, -1, -1, 1, 1}, dxb[] = {0, 0, -1, 1, -1, 1, -1, 1};

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);

    int n, m; cin >> n >> m;
    vector<vector<int>> grid(n, vector<int>(m));
    for(auto &x : grid) for(auto &y : x) cin >> y;

    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            if(grid[i][j] == 0)
                for(int k = 0; k < 8; k++) {
                    int ny = i + dyb[k], nx = j + dxb[k];
                    if(ny < 0 || ny >= n || nx < 0 || nx >= m) continue;
                    if(grid[ny][nx] == 0) continue;
                    grid[ny][nx] = 2;
                }
    
    queue<pair<int, int>> q;
    vector<vector<ll>> dist(n, vector<ll>(m, INF));
    for(int i = 0; i < n; i++) {
        if(grid[i][0] != 1) continue;
        q.push({i, 0});
        dist[i][0] = 0;
    }

    while(!q.empty()) {
        auto [y, x] = q.front(); q.pop();
        for(int k = 0; k < 4; k++) {
            int ny = y + dy[k], nx = x + dx[k];
            if(ny < 0 || ny >= n || nx < 0 || nx >= m) continue;
            if(grid[ny][nx] != 1) continue;
            if(dist[ny][nx] != INF) continue;
            dist[ny][nx] = min(dist[ny][nx], dist[y][x] + 1);
            q.push({ny, nx});
        }
    }

    ll ans = INF;
    for(int i = 0; i < n; i++)
        ans = min(ans, dist[i][m-1]);

    cout << (ans == INF ? -1 : ans + 1) << '\n';

    return 0;
}