Submission

Score: 0

User: faofao

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

Language: cpp

Time: 1.094 second

Submitted On: 2026-03-12 11:43:02

#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,0,0,1} ;
int dj[4] = {0,-1,1,0} ;
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(int si,int sj,int round){
    vector<vector<bool>> vis(mxN, vector<bool>(mxN,0)) ;
    queue<tuple<int,int,int>> q ; // i,j,round
    q.push({si,sj,1}) ;
    vis[si][sj] = 1 ;
    while(!q.empty()){
        auto [i,j,round] = q.front() ;
        q.pop() ; 
        if(j==m-1){
            mn = min(mn,round) ;
            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(vis[ni][nj] || grid[ni][nj] == 0) continue;
            vis[ni][nj] = 1 ;
            q.push({ni,nj,round+1}) ;
        }
    }

}

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