Submission

Score: 100

User: kenmuay

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

Language: cpp

Time: 0.057 second

Submitted On: 2026-03-06 21:38:21

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

const int maxn = 1e3+10;
bool c[maxn][maxn];
int visited[maxn][maxn];

struct GRID {
    int i,j;
};
queue<GRID> qu;

int di[8] = {-1,0,1,0,-1,1,1,-1};
int dj[8] = {0,1,0,-1,1,1,-1,-1};

int main() {
    cin.tie(nullptr)->sync_with_stdio(0);
    int n,m;
    cin >> n >> m;
    vector<GRID> bomb;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            cin >> c[i][j];
            if(!c[i][j]) bomb.push_back({i, j});
        }
    }

    for(auto x : bomb){
        int i = x.i;
        int j = x.j;
        for(int k=0; k<8; k++){
            int ii = i+di[k];
            int jj = j+dj[k];

            if(ii < 1 || jj < 1 || ii > n || jj > m) continue;
            c[ii][jj] = false;
        }
    }

    for(int i=1; i<=n; i++){
        if(!c[i][1]) continue;
        qu.push({i, 1});
        visited[i][1] = 1;
    }

    while(!qu.empty()){
        int i = qu.front().i;
        int j = qu.front().j;
        // cout << i << ' ' << j << '\n';
        qu.pop();

        if(j == m){
            cout << visited[i][j] << '\n';
            return 0;
        }
        for(int k=0; k<4; k++){
            int ii = i+di[k];
            int jj = j+dj[k];

            if(ii < 1 || jj < 1 || ii > n || jj > m) continue;
            if(!c[ii][jj]) continue;
            if(visited[ii][jj] > 0) continue;

            qu.push({ii, jj});
            visited[ii][jj] = visited[i][j]+1;
        }
    }
    cout << -1 << '\n';
}