Submission

Score: 0

User: iij

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

Language: cpp

Time: 0.097 second

Submitted On: 2025-10-23 16:59:38

#include <bits/stdc++.h>

#define vi vector<int>
#define vvi vector<vi>
using namespace std;

int m, n, dirs[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
int bombDirs[8][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {-1, -1}, {1, -1}, {-1, 1}};

int bfs(vvi v) {
    queue<vi> q;
    for (int i = 0; i < m; i++) if (v[i][0]) q.push({i, 0, 1});

    vector<vector<bool>> visited(m, vector<bool>(n, 0));

    while (!q.empty()) {
        auto cur = q.front();
        int row = cur[0], col = cur[1], dist = cur[2];
        q.pop();

        if (col == n-1) return dist;

        for (auto d : dirs) {
            int nrow = row + d[0], ncol = col + d[1];
            if (nrow >= 0 && ncol >= 0 && nrow < m && ncol < n && v[nrow][ncol] && !visited[nrow][ncol]) {
                visited[nrow][ncol] = 1;
                q.push({nrow, ncol, dist+1});
            }
        }
    }

    return -1;
}

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

    vvi v(m, vi(n));
    for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) cin >> v[i][j];

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (!v[i][j]) {
                for (auto d : bombDirs) {
                    int nrow = i + d[0], ncol = j + d[1];
                    if (nrow >= 0 && ncol >= 0 && nrow < m && ncol < n) v[nrow][ncol] = -1;
                }
            }
        }
    }
    for (auto &i : v) for (auto &j : i) if (j == -1) j = 0;

    cout << bfs(v);
}