Submission

Score: 100

User: kimza

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

Language: cpp

Time: 0.052 second

Submitted On: 2026-03-07 00:12:05

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    int n,m;
    cin >> n >> m;
    int mp[n][m];
    vector<vector<int>> visited(n,vector<int>(m,INF));
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin >> mp[i][j];
        }
    }
    //find 0 
    vector<pair<int,int>> check;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(mp[i][j]==0) check.push_back({i,j});
        }
    }

    //set area around 0 to 2
    
    for(auto& x:check){
        int i = x.first;
        int j = x.second;

        mp[i][j] = 2;
        if(i+1<n) mp[i+1][j] = 2;
        if(j+1<m) mp[i][j+1] = 2;
        if(i-1>=0) mp[i-1][j] = 2;
        if(j-1>=0) mp[i][j-1] = 2;
        if(i+1<n && j+1<m) mp[i+1][j+1] = 2;
        if(i-1>=0 && j-1>=0) mp[i-1][j-1] = 2;
        if(i+1<n && j-1>=0) mp[i+1][j-1] = 2;
        if(i-1>=0 && j+1<m) mp[i-1][j+1] = 2;
    }
    // for(int i=0;i<n;i++){
    //     for(int j=0;j<m;j++){
    //         cout << mp[i][j] << " ";
    //     }
    //     cout << "\n";
    // }

    //start from [i][0] that mp[i][0] == 1
    queue<pair<int,int>> q;
    for(int i=0;i<n;i++){
        if(mp[i][0]==1) {
            q.push({i,0});
            visited[i][0] = 1;
        }
    }
    //bfs
    while(!q.empty()){
        int y = q.front().first;
        int x = q.front().second;
        q.pop();
        if(y+1<n && mp[y+1][x]==1 && visited[y+1][x] == INF){
            q.push({y+1,x});
            visited[y+1][x] = visited[y][x]+1;
        }
        if(x+1<m && mp[y][x+1]==1 && visited[y][x+1] == INF){
            q.push({y,x+1});
            visited[y][x+1] = visited[y][x]+1;
        }
        if(y-1>=0 && mp[y-1][x]==1 && visited[y-1][x] == INF){
            q.push({y-1,x});
            visited[y-1][x] = visited[y][x]+1;
        }
        if(x-1>=0 && mp[y][x-1]==1 && visited[y][x-1] == INF){
            q.push({y,x-1});
            visited[y][x-1] = visited[y][x]+1;
        }
    }
    
    // for(int i=0;i<n;i++){
    //     for(int j=0;j<m;j++){
    //         cout << visited[i][j] << " ";
    //     }
    //     cout << "\n";
    // }

    //find min from the furthest right;
    int min = INF;
    for(int i=0;i<n;i++){
        if(visited[i][m-1] < min) min = visited[i][m-1];
    }
    if(min<INF) cout << min;
    else cout << "-1";

   
    return 0;
}