Submission

Score: 100

User: mantaggez

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

Language: cpp

Time: 0.065 second

Submitted On: 2026-03-12 17:45:05

#include <bits/stdc++.h>

using namespace std;
using pii = pair<int, int>;

const int nx = 1e3+5;
const int INF = 1e9;

int n, m;
int dist[nx][nx], grid[nx][nx], bad[nx][nx], vs[nx][nx];
int di8[] = {-1, -1, -1, 0, 0, 1, 1, 1}, di4[] = {-1, 0, 0, 1};
int dj8[] = {-1, 0, 1, -1, 1, -1, 0, 1}, dj4[] = {0, -1, 1, 0};
queue<pii> q;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin >> n >> m;
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            cin >> grid[i][j];
            dist[i][j] = INF;
        }
    }

    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            if(grid[i][j] == 0)
            for(int d=0;d<8;d++) {
                int ni = i + di8[d], nj = j + dj8[d];
                bad[ni][nj] = 1;
            }
        }
    }

    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            if(grid[i][j] == 1 && bad[i][j] == 1)
                grid[i][j] = 0;
        }
    }

    for(int i=1;i<=n;i++) if(grid[i][1] == 1) q.push({i, 1}), dist[i][1] = 1;

    while(!q.empty())
    {
        auto [i, j] = q.front();
        q.pop();
        if(vs[i][j]) continue;
        vs[i][j] = 1;
        for(int d=0;d<4;d++)
        {
            int ni = i + di4[d], nj = j + dj4[d];
            if(1 <= ni && ni <= n && 1 <= nj && nj <= m && grid[ni][nj] == 1)
            {
                if(dist[ni][nj] > dist[i][j] + 1)
                {
                    dist[ni][nj] = dist[i][j] + 1;
                    q.push({ni, nj});
                }
            }
        }
    }

    int res = INF;
    for(int i=1;i<=n;i++) res = min(res, dist[i][m]);

    cout << (res == INF ? -1 : res);
    
    return 0;
}