Submission

Score: 100

User: faofao

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

Language: cpp

Time: 0.052 second

Submitted On: 2026-03-12 11:51:50

#include <bits/stdc++.h>
using namespace std;
int n,m ;
const int mxN = 1003 ;
int grid[mxN][mxN] ;
int dx[8] = {1,1,1,0,0,-1,-1,-1} ;
int dy[8] = {-1,0,1,-1,1,-1,0,1} ;
int di[4] = {-1,1,0,0} ;
int dj[4] = {0,0,-1,1} ;
int mn = INT_MAX ;

void setupp(){
    vector<vector<int>> temp(mxN, vector<int>(mxN,0));
    for(int i=0 ; i<n ; i++){
        for(int j=0 ; j<m ; j++){
            int x ; cin >> x;
            grid[i][j] = x ;
            temp[i][j] = grid[i][j] ;
        }
    }
    for(int i=0 ; i<n ; i++){
        for(int j=0 ; j<m ; j++){
            if(grid[i][j]==0){
                temp[i][j] = 0 ;
                for(int k=0 ; k<8 ; k++){
                    int ni = i + dx[k];
                    int nj = j + dy[k];
                    if(ni >= 0 && ni < n && nj >= 0 && nj < m){
                        temp[ni][nj] = 0 ;
                    }
                }
            }
        }
    }
    for(int i=0 ; i<n ; i++){
        for(int j=0 ; j<m ; j++){
            grid[i][j] = temp[i][j];
        }
    }
}

void bfs(){
    vector<vector<int>> dist(n, vector<int>(m, -1));
    queue<pair<int,int>> q ; // i,j,round
    for(int i=0 ; i<n ; i++){
        if(grid[i][0]==1){
            dist[i][0] =1 ;
            q.push({i,0}) ;
        }
    }
    while(!q.empty()){
        auto [i,j] = q.front() ;
        q.pop() ; 
        if(j==m-1){
            mn = min(mn,dist[i][j]) ;
            return ;
        }

        for(int k=0 ; k<4 ; k++){
            int ni = i+di[k] ;
            int nj = j+dj[k] ;
            if(ni<0 || nj<0 || ni>=n || nj>=m)continue;
            if(grid[ni][nj]==0 || dist[ni][nj] !=-1) continue;
            dist[ni][nj] = dist[i][j]+1 ;
            q.push({ni,nj}) ;
        }
    }

}

int main(){
    ios::sync_with_stdio(0),cin.tie(0) ;
    cin >> n >> m ;
    setupp() ;
    bfs() ;
    if(mn==INT_MAX) cout << -1;
    else cout << mn ;
}