Submission

Score: 100

User: Quaoar

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

Language: cpp

Time: 0.109 second

Submitted On: 2026-03-06 20:00:31

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

int dx[] = {-1 , 1 , 0 , 0};
int dy[] = {0 , 0 , -1 , 1};

int bfs(vector<vector<int>> &mp){
    int n = mp.size();
    int m = mp[0].size();
    vector<vector<int>> dist(n , vector<int>(m , 0));
    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 x = q.front().first;
        int y = q.front().second;
        q.pop();
        if (y == m - 1){
            return dist[x][y];
        }

        for (int i = 0 ; i < 4 ; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx < 0 || nx >= n || ny < 0 || ny >= m){
                continue;
            }

            if (mp[nx][ny] != 1){
                continue;
            }

            if (dist[nx][ny] == 0){
                dist[nx][ny] = dist[x][y] + 1;
                q.push({nx,ny});
            }
        }
    }
    return -1;
}

int main(){
    int n , m;
    cin >> n >> m;

    vector <vector <int>> mp(n , vector<int>(m));

    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 dx = -1 ; dx <= 1; dx++){
                    for (int dy = -1 ; dy <= 1 ; dy++){
                        int nx = i + dx;
                        int ny = j + dy;
                        if (nx < 0 || nx >= n || ny < 0 || ny >= m ){
                            continue;
                        }
                        if (mp[nx][ny] != 0)
                            mp[nx][ny] = 2;

                    }
                }
            }
        }
    }
    cout << bfs(mp);
    return 0;
}