Submission

Score: 0

User: kd

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

Language: cpp

Time: 0.046 second

Submitted On: 2026-01-04 15:04:35

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

int x[] = {0, 0, 1, 1, 1, -1, -1, -1};
int y[] = {1, -1, 1, -1, 0, 1, -1, 0};
int dr[] = {-1, 1, 0, 0};
int dc[] = {0, 0, -1, 1};

int main(){
    cin.tie(0)->sync_with_stdio(0);
    int n, m;
    cin>>n>>m;
    int arr[n][m];
    vector<vector<int> > grid(n, vector<int>(m, 1));
    vector<vector<int> > vst(n, vector<int>(m, 0));
    queue<pair<pair<int, int>, int>> q;

    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++)  cin>>arr[i][j];
    }

    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(grid[i][j]==1){
                if(arr[i][j]==0){
                    grid[i][j] = 0;
                    for(int k=0;k<8;k++){
                        int ni = i + y[k];
                        int mi = j + x[k];
                        if (ni>=0 && ni<n && mi>=0 && mi<m){
                            grid[ni][mi] = 0;
                        } } } } } }
                        
    for(int i=0;i<n;i++){
        if(grid[i][0]){
            q.push({{i, 0}, 1});
            vst[i][0] = 1;
        }
    }
    while(!q.empty()){
        int r = q.front().first.first;
        int c = q.front().first.second;
        int d = q.front().second;
        q.pop();
        if(c==m-1){
            cout<<d;
            return 0;
        }
        for(int i=0;i<4;i++){
            int nr = r + dr[i];
            int nc = c + dc[i];
            if (nr>=0 && nr<n && nc>=0 && nc<m && grid[nr][nc] && !vst[nr][nc]) {
                q.push({{nr, nc}, d+1});
                vst[nr][nc] = 1;
            }
        }
    }
    cout<<-1;
}