Submission

Score: 100

User: Quaoar

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

Language: cpp

Time: 0.068 second

Submitted On: 2026-03-11 19:44:43

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

int bfs(vector <vector<int>> &grid){
    int n = grid.size();
    int m = grid[0].size();
    queue <pair <int,int>> q;
    vector <vector<int>> dist(n , vector<int>(m , 0));
    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(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n , m;
    cin >> n >> m;
    vector <vector<int>> grid(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);
    return 0;
}