Submission

Score: 100

User: Zonezonee

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

Language: cpp

Time: 0.115 second

Submitted On: 2025-12-07 14:20:29

#include <bits/stdc++.h>
using namespace std;
const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};

int a[1010][1010], n, m, dist[1010][1010];
bool valid(int x, int y){
    bool bomb = false;
    for(int i = -1; i <= 1; ++i){
        for(int j = -1; j <= 1; ++j){
            if(x+i <= 0 || y+j <= 0 || x+i > n || y+j > m) continue;
            if(a[x+i][y+j] == 0) bomb = 1;
        }
    }
    return (x > 0 && y > 0 && x <= n && y <= m && !bomb);
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    queue<tuple<int, int, int>> q;
    memset(dist, 0x1f, sizeof dist);
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= m; ++j){
            if(j == 1) q.push({i, j, dist[i][j] = 1});
            cin >> a[i][j];
        }
    }
    while(!q.empty()){
        auto [x, y, d] = q.front(); q.pop();
        for(int i = 0; i < 4; ++i){
            int xx = x+dx[i], yy = y+dy[i];
            if(valid(xx, yy)){
                if(dist[xx][yy] > d+1)
                    q.push({xx, yy, dist[xx][yy] = d+1});
            }
        }
    }
    int ans = 1e7;
    for(int i = 1; i <= n; ++i){
        ans = min(ans, dist[i][m]);
    }
    cout << (ans == 1e7 ? -1 : ans) << '\n';
}