Submission

Score: 0

User: ztmy_

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

Language: cpp

Time: 0.003 second

Submitted On: 2026-03-16 11:39:30

#include <bits/stdc++.h>
using namespace std;
int dx[] = {1,-1,0,0,1,-1,1,-1};
int dy[] = {0,0,1,-1,1,-1,-1,1};
int sx[] = {1,-1,0,0};
int sy[] = {0,0,1,-1};
queue<pair<int, int>> idx;
vector<vector<bool>> visited;
vector<vector<int>> dist;
vector<vector<int>> arr;

int bfs(int row, int col){
    int m = 1e9;
    while(!idx.empty()){
        auto cur = idx.front();
        int y = cur.first;
        int x = cur.second;
        idx.pop();
        if (x == col-1){
            if (dist[y][x] < m) m = dist[y][x];
        }
        for (int i = 0; i < 4; i++){
            int Ay = y + sy[i];
            int Ax = x + sx[i];
            if (Ay >= 0 && Ay < row && Ax >= 0 && Ax < col && !visited[Ay][Ax] && arr[Ay][Ax] == 1){
                idx.push({Ay, Ax});
                visited[Ay][Ax] = true;
                dist[Ay][Ax] = dist[y][x]+1;
            }
        }
    }
    return m;
}

int main(){
    int row, col;
    cin >> row >> col;
    arr.assign(row, vector<int>(col));
    visited.assign(row, vector<bool>(col, false));
    dist.assign(row, vector<int>(col, -1));
    for (int i = 0; i < row; i++){
        for (int j = 0; j < col; j++) cin >> arr[i][j];
    }
    vector<vector<int>> blocked = arr;
    for (int i = 0; i < row; i++){
        for (int j = 0; j < col; j++){
            if (arr[i][j] == 0){
                for (int k = 0; k < 8; k++){
                    int ny = i + dy[k];
                    int nx = j + dx[k];
                    if (ny >= 0 && ny < row && nx >= 0 && nx < col){
                        blocked[ny][nx] = 0;
                    }
                }
            }
        }
    }
    arr = blocked;
    for (int i = 0; i < row; i++){
        if (arr[i][0] == 1){
            idx.push({i, 0});
            dist[i][0] = 1;
            visited[i][0] = true;
        }
    }
    cout << bfs(row, col);
}