Submission

Score: 0

User: Pera

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

Language: cpp

Time: 1.107 second

Submitted On: 2025-05-24 12:35:24

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

void preprocess_unsafe_cells(int n, int m, const vector<vector<int>> &grid, vector<vector<int>> &min_distance_to_grid) {
    for (int r = 0; r < n; ++r) {
        for (int c = 0; c < m; ++c) {
            if (grid[r][c] == 0) {
                min_distance_to_grid[r][c] = 0;
            }

            vector<int> rTraverse = {-1, -1, -1, 0, 0, 1, 1, 1};
            vector<int> cTraverse = {-1, 0, 1, -1, 1, -1, 0, 1};

            for (int i = 0; i < 8; ++i) {
                int newR = r + rTraverse[i];
                int newC = c + cTraverse[i];

                if (newR >= 0 && newR < n && newC >= 0 && newC < m && grid[newR][newC] == 0) {
                    min_distance_to_grid[r][c] = 0;
                    break;
                }
            }
        }
    }
}

void dfs(vector<vector<int>> &grid, vector<vector<int>> &min_distance_to_grid, int r, int c, int current_dist) {
    if (r < 0 || r >= grid.size() || c < 0 || c >= grid[r].size() || min_distance_to_grid[r][c] <= current_dist) {
        return;
    }

    if (min_distance_to_grid[r][c] == 0) {
        return;
    }

    min_distance_to_grid[r][c] = current_dist;

    vector<int> dr = {-1, 0, 0, 1};
    vector<int> dc = {0, -1, 1, 0};

    for (int i = 0; i < 4; ++i) {
        int newR = r + dr[i];
        int newC = c + dc[i];

        dfs(grid, min_distance_to_grid, newR, newC, current_dist + 1);
    }
}

int main() {
    ios_base::sync_with_stdio(false);

    int n, m;
    cin >> n >> m;

    vector<vector<int>> grid_input(n, vector<int>(m));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> grid_input[i][j];
        }
    }

    vector<vector<int>> min_distance_to_grid(n, vector<int>(m, INT_MAX));

    preprocess_unsafe_cells(n, m, grid_input, min_distance_to_grid);

    for (int i = 0; i < n; ++i) {
        if (min_distance_to_grid[i][0] != 0) {
            dfs(grid_input, min_distance_to_grid, i, 0, 1);
        }
    }

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

    if (min_path_len == INT_MAX) {
        cout << -1 << '\n';
    } else {
        cout << min_path_len << '\n';
    }
}