Submission

Score: 0

User: iij

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

Language: cpp

Time: 0.087 second

Submitted On: 2025-10-23 18:09:41

#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<tuple<int, int, int>> 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 = get<0>(cur), col = get<1>(cur), dist = get<2>(cur);
        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] == 1 && !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] = 9;
                }
            }
        }
    }

    cout << bfs(v);
}