Submission

Score: 100

User: Pera

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

Language: cpp

Time: 0.226 second

Submitted On: 2025-05-24 13:36:13

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

void markcell(vector<vector<int>> &grid, vector<vector<int>> &min_dist);

int main() {
    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) {
            int num; cin >> num;
            grid[i][j] = num;
        }
    }

    // mark every cell as not visited right now
    vector<vector<int>> min_dist(n, vector<int>(m, INT_MAX));

    // Set the minimum dist for first box to 1, although the below func will mark as invalid anyways if that tile is invalid
    for (int i = 0; i < n; ++i) {
        min_dist[i][0] = 1;
    }

    // pre mark cell that is a bomb/invalid
    markcell(grid, min_dist);

    queue<pair<int, int>> q;

    // bfs for first column
    for (int i = 0; i < n; ++i) {
        if (min_dist[i][0] != 0) q.push({i, 0});
    }

    vector<int> tr = {1, 0, 0, -1};
    vector<int> tc = {0, -1, 1, 0};

    // bfs
    while (!q.empty()) {
        pair<int, int> pos = q.front();
        q.pop();

        for (int i = 0; i < 4; ++i) {
            int newR = pos.first + tr[i];
            int newC = pos.second + tc[i];

            // out of bounds
            if (newR < 0 || newR >= n || newC < 0 || newC >= m) continue;
            // bomb
            else if (grid[newR][newC] == 0) continue;
            // not bomb
            else {
                // not visited
                if (min_dist[newR][newC] == INT_MAX) {
                    min_dist[newR][newC] = min_dist[pos.first][pos.second] + 1;
                    q.push({newR, newC});
                }
                // visited
                else {
                    // if the new min dist is smaller gotta push it again
                    if (min_dist[newR][newC] > min_dist[pos.first][pos.second] + 1) {
                        min_dist[newR][newC] = min_dist[pos.first][pos.second] + 1;
                        q.push({newR, newC});
                    }
                }
            }
        }
    }

    int mi = INT_MAX;
    for (int i = 0; i < n; ++i) {
        if (min_dist[i][m-1] != 0) {
            mi = min(mi, min_dist[i][m - 1]);
        }
    }

    mi == INT_MAX ? cout << -1 << '\n' : cout << mi << '\n';

    // for (int i = 0; i < n; ++i) {
    //     for (int j = 0; j < m; ++j) {
    //         cout << min_dist[i][j] << ' ';
    //     }
    //     cout << '\n';
    // }
}

void markcell(vector<vector<int>> &grid, vector<vector<int>> &min_dist) {
    vector<int> tr = {1, 1, 1, 0, 0, -1, -1, -1};
    vector<int> tc = {-1, 0, 1, -1, 1, 1, 0, -1};
    for (int i = 0; i < grid.size(); ++i) {
        for (int j = 0; j < grid[i].size(); ++j) {
            if (grid[i][j] == 0) {
                min_dist[i][j] = 0;
                for (int k = 0; k < 8; ++k) {
                    int newR = i + tr[k];
                    int newC = j + tc[k];

                    if (newR < 0 || newR >= grid.size() || newC < 0 || newC >= grid[0].size()) continue;

                    min_dist[newR][newC] = 0;
                }
            }
        }
    }
}