Submission

Score: 100

User: Gunto

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

Language: cpp

Time: 0.060 second

Submitted On: 2026-03-04 15:16:23

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e3;
int visited[maxn][maxn];


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

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

int main(){
    cin.tie(nullptr)->sync_with_stdio(0);
   int r, c;
    cin >> r >> c;
    vector<vector<int>> m(r, vector<int>(c, 0));
    
    for(int i=0;i<r;++i){
        for(int j=0;j<c;++j){
            cin>>m[i][j];
        }
    }
    //solve
     vector<vector<int>> ans = m;
    for(int i=0;i<r;++i){
        for(int j=0;j<c;++j){
            bool ch=0;
            for(int k=max(0,i-1);k<=min(r-1,i+1);++k){
                for(int kk=max(0,j-1);kk<=min(c-1,j+1);++kk){
                    if(m[k][kk]==0){
                         ans[i][j]=0;
                         ch=1;
                         break;
                    }
                }
                if(ch==1) break;
            }
        }
    }

    // for(int i=0;i<r;++i){
    //     for(int j=0;j<c;++j){
    //         cout<<ans[i][j];
    //     }cout<<"\n";
    // }
    //this is ok
    for(int i=0; i<r; i++){
        qu.push({i,0});
        visited[i][0] = 1;
    }
    
    
    while(!qu.empty()){
        int i = qu.front().i;
        int j = qu.front().j;
        qu.pop();

        if(j == c-1){
            cout << visited[i][j] ;
            return 0;
        }
        for(int k=0; k<4; k++){
            int ii = i+di[k];
            int jj = j+dj[k];

            if(ii < 0 || jj < 0 || ii > r-1 || jj > c-1) continue;
            if(visited[ii][jj]) continue;
            if(!ans[ii][jj]) continue;

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

    return 0;
}