Submission

Score: 100

User: Overlord12345

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

Language: cpp

Time: 0.088 second

Submitted On: 2025-12-07 13:50:39

#include <vector>
#include<iostream>
#include<queue>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

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

    int dx8[8] = {-1,-1,-1,0,0,1,1,1};
    int dy8[8] = {-1,0,1,-1,1,-1,0,1};
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (a[i][j] == 0) {
                safe[i][j] = false;
                for (int d = 0; d < 8; d++) {
                    int nx = i + dx8[d];
                    int ny = j + dy8[d];
                    if (nx >= 0 && nx < N && ny >= 0 && ny < M)
                        safe[nx][ny] = false;
                }
            }
        }
    }

    queue<pair<int,int>> q;
    vector<vector<int>> dist(N, vector<int>(M, -1));
    for (int i = 0; i < N; i++) {
        if (safe[i][0]) {
            q.push({i, 0});
            dist[i][0] = 1;   
        }
    }

    int dx[4] = {-1, 1, 0, 0};
    int dy[4] = {0, 0, -1, 1};

    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();

        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d];
            int ny = y + dy[d];

            if (nx >= 0 && nx < N && ny >= 0 && ny < M) {
                if (safe[nx][ny] && dist[nx][ny] == -1) {
                    dist[nx][ny] = dist[x][y] + 1;
                    q.push({nx, ny});
                }
            }
        }
    }
    int ans = -1;
    for (int i = 0; i < N; i++) {
        if (dist[i][M-1] != -1) {
            if (ans == -1 || dist[i][M-1] < ans)
                ans = dist[i][M-1];
        }
    }
    cout << ans;
    return 0;
}