Submission

Score: 0

User: ztmy_

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

Language: cpp

Time: 0.002 second

Submitted On: 2026-03-16 11:24:50

#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;

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]){
                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;
    vector<vector<int>> arr(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];
    }
    for (int i = 0; i < row; i++){
        for (int j = 0; j < col; j++){
            if (arr[i][j] == 0 && !visited[i][j]){
                visited[i][j] = true;
                for (int k = 0; k < 8; k++){
                    if (i+dy[k] >= 0 && i+dy[k] < row && j+dx[k] >= 0 && j+dx[k] < col){
                        arr[i+dy[k]][j+dx[k]] = 0;
                        visited[i+dy[k]][j+dx[k]] = true;
                    }
                }
            }
        }
    }
    for (int i = 0; i < row; i++){
        if (arr[i][0] == 1){
            idx.push({i, 0});
            dist[i][0] = 1;
        }
    }
    cout << bfs(row, col);
}