Submission

Score: 100

User: kimza

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

Language: cpp

Time: 0.058 second

Submitted On: 2026-03-07 00:04:40

#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 
    //set area around 0 to 2
    vector<pair<int, int>> zeros;
    for(int i=0; i<n; i++) {
        for(int j=0; j<m; j++) {
            if(mp[i][j] == 0) zeros.push_back({i, j});
        }
    }

    for(auto& p : zeros) {
        for(int di = -1; di <= 1; di++) {
            for(int dj = -1; dj <= 1; dj++) {
                int ni = p.first + di, nj = p.second + dj;
                if(ni >= 0 && ni < n && nj >= 0 && nj < m) {
                    mp[ni][nj] = 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;
}