Submission

Score: 0

User: Quaoar

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

Language: cpp

Time: 0.607 second

Submitted On: 2026-03-11 19:37:54

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

vector <vector<int>> grid;
vector <vector<int>> dist;
int n , m;
int bfs(vector <vector<int>> &grid ,vector <vector<int>> &dist){
    queue <pair <int,int>> q;
    for (int i = 0 ; i < n ; i++){
        if (grid[i][0] == 1) q.push({i,0});
        dist[i][0] = 1;
    }
    int dx[] = {-1,1,0,0};
    int dy[] = {0,0,-1,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 (grid[nx][ny] != 1) continue;

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

int main(){
    cin >> n >> m;
    grid.resize(n , vector<int> (m));
    dist.resize(n , vector<int>(m)); 
    for (int i = 0 ; i < n ; i++){
        for (int j = 0 ; j <m ; j++){
            cin >> grid[i][j];
        }
    }
    for (int i = 0 ; i < n ; i++){
        for (int j = 0 ; j <m ; j++){
            if (grid[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 (grid[nx][ny] == 0) continue;

                        grid[nx][ny] = 2;
                    }
                }
            }
        }
    }
    cout << bfs(grid , dist) << "\n";
    return 0;
}