Submission

Score: 100

User: syndrxme

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

Language: cpp

Time: 0.099 second

Submitted On: 2026-03-14 11:58:22

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

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

int main(){
    int n,m;
    cin>>n>>m;
    vector<vector<int>> grid(n,vector<int>(m));
    vector<pair<int,int>> bomb;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>grid[i][j];
            if(grid[i][j]==0){
                bomb.push_back({i,j});
            }
        }
    }
    for(auto const& p:bomb){
        for(int dy=-1;dy<=1;dy++){
            for(int dx=-1;dx<=1;dx++){
                int nr = p.first+dy;
                int nc = p.second+dx;
                if(nr>=0 && nr<n && nc>=0 && nc<m && grid[nr][nc]!=0){
                    grid[nr][nc]=0;
                }
            }
        }
    }
    // for(int i=0;i<n;i++){
    //     for(int j=0;j<m;j++){
    //         cout<<grid[i][j]<<" ";
    //     }
    //     cout<<"\n";
    // }
    queue<pair<pair<int,int>,int>> q;
    for(int i=0;i<n;i++){
        if(grid[i][0]==1){
            q.push({{i,0},1});
        }
    }

    while(q.empty()==false){
        int r= q.front().first.first;
        int c = q.front().first.second;
        int dist = q.front().second;
        q.pop();
        if(c==m-1){
            cout<<dist;
            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]==1){
                q.push({{nr,nc},dist+1});
                grid[nr][nc]=0;
            }
        }
    }
    cout<<-1;
    return 0;
}