Submission

Score: 0

User: Quaoar

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

Language: cpp

Time: 0.086 second

Submitted On: 2026-03-06 19:58:38

#include <bits/stdc++.h>
using namespace std;

vector <vector <int>> mp;
vector <vector <int>> dist;
vector <int> ans;
int x[] = {-1 , 1 , 0 , 0};
int y[] = {0 , 0 , 1 , -1};

void bfs (vector<vector<int>>mp){

    int n = mp.size();
    int m = mp[0].size();
    queue<pair<int,int>> q;

    for (int i = 0 ; i < n ; i++){
        if (mp[i][0] == 1){
            q.push({i , 0});
            dist[i][0] = 1;
        }
    }

    while (!q.empty()){
        int r = q.front().first;
        int c = q.front().second;
        q.pop();

        if (c == m - 1){
            ans.push_back(dist[r][c]);
        }

        for (int i = 0 ; i < 4 ; i++){
            int nr = r + x[i];
            int nc = c + y[i];

            if (nr < 0 || nr >= n || nc < 0 || nc >= m)
                continue;

            if (mp[nr][nc] != 1)
                continue;

            if (dist[nr][nc] == -1){
                dist[nr][nc] = dist[r][c] + 1;
                q.push({nr , nc});
            }
        }
    }
}
int main(){
    int n ,m;
    cin >> n >> m;
    mp.resize(n , vector<int>(m));
    dist.resize(n , vector<int>(m , -1));
    for (int i = 0 ; i < n ; i++){
        for (int j = 0 ; j < m ; j++){
            cin >> mp[i][j];
        }
    }

    for (int i = 0 ; i < n ; i++){
        for (int j = 0 ; j < m ; j++){
            if (mp[i][j] == 0){
                for (int x = -1 ; x <= 1 ; x++){
                    for (int y = -1 ; y <= 1 ;y++){
                        if (i + x < 0 || i + x >= n || j + y < 0 || j + y >= m)
                            continue;
                        mp[i + x][j + y] = -1;
                    }
                }
                
            }
        }
    }
    bfs(mp);
    int mn = 10000000;
    if (ans.empty()){
        cout << -1;
        return 0;
    }
    for (int i = 0 ; i < ans.size() ; i++){
        mn = min(ans[i] , mn);
    }

    cout << mn;
    return 0;
}