Submission

Score: 100

User: PEPSEALSEA

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

Language: cpp

Time: 0.084 second

Submitted On: 2025-12-07 14:40:32

#include <bits/stdc++.h>

using namespace std;

const int dr[] = {-1, 1, 0, 0}; 
const int dc[] = {0, 0, -1, 1};

const int dr8[] = {-1, -1, -1, 0, 0, 1, 1, 1};
const int dc8[] = {-1, 0, 1, -1, 1, -1, 0, 1};

bool isValid(int r, int c, int N, int M) {
    return r >= 0 && r < N && c >= 0 && c < M;
}

void solve() {
    int N, M;

    if (!(cin >> N >> M)) return;

    vector<vector<int>> grid(N, vector<int>(M));
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            cin >> grid[i][j];
        }
    }

    vector<vector<bool>> is_safe(N, vector<bool>(M, true));

    for (int r = 0; r < N; ++r) {
        for (int c = 0; c < M; ++c) {

            if (grid[r][c] == 0) {
                is_safe[r][c] = false;

                for (int k = 0; k < 8; ++k) {
                    int nr = r + dr8[k];
                    int nc = c + dc8[k];

                    if (isValid(nr, nc, N, M)) {
                        is_safe[nr][nc] = false;
                    }
                }
            }
        }
    }

    vector<vector<int>> dist(N, vector<int>(M, -1));
    queue<pair<int, int>> q;

    for (int r = 0; r < N; ++r) {
        if (is_safe[r][0]) {
            q.push({r, 0});
            dist[r][0] = 1; 

        }
    }

    while (!q.empty()) {
        pair<int, int> current = q.front();
        q.pop();
        int r = current.first;
        int c = current.second;

        for (int k = 0; k < 4; ++k) {
            int nr = r + dr[k];
            int nc = c + dc[k];

            if (isValid(nr, nc, N, M) && 
                is_safe[nr][nc] && 
                dist[nr][nc] == -1) {

                dist[nr][nc] = dist[r][c] + 1;
                q.push({nr, nc});
            }
        }
    }

    int min_steps = -1;

    for (int r = 0; r < N; ++r) {
        if (dist[r][M - 1] != -1) {
            if (min_steps == -1 || dist[r][M - 1] < min_steps) {
                min_steps = dist[r][M - 1];
            }
        }
    }

    cout << min_steps << endl;
}

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    solve();

    return 0;
}