Submission

Score: 100

User: Kx

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

Language: cpp

Time: 0.099 second

Submitted On: 2026-03-19 08:35:40

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

typedef vector<vector<int>> vvi;
typedef vector<pair<int, int>> vpii;
vector<vector<bool>> visited;

const int mx = 1e8;

int n, m;
int dx[] = {0, -1, 0, 1, -1, 1, -1, 1};
int dy[] = {-1, 0, 1, 0, -1, -1, 1, 1};
vvi dist;
vvi mp;
vpii p;

bool cp(int x, int y, int n, int m) {
    return x >= 0 && x < n && y >= 0 && y < m;
}

void bfs() {
    queue<pair<int, int>> q;

    for(int i = 0; i < n; ++i) {
        if(mp[i][0] != 0) {
            q.push({i, 0});
            dist[i][0] = 1;
            visited[i][0] = true;
        }
    }

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

        for(int i = 0; i < 4; ++i) {
            int sx = x + dx[i];
            int sy = y + dy[i];

            if(cp(sx, sy, n, m)) {
                if(!visited[sx][sy] && mp[sx][sy] != 0) {
                    visited[sx][sy] = true;
                    dist[sx][sy] = dist[x][y] + 1;
                    q.push({sx, sy});
                }
            }
        }
    }
}

int main() {
    cin >> n >> m;
    mp.assign(n, vector<int>(m));
    visited.assign(n, vector<bool>(m, false));
    dist.assign(n, vector<int>(m, mx));

    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < m; ++j) {
            cin >> mp[i][j];
            if(mp[i][j] == 0) p.push_back({i, j});
        }
    }

    for(auto [x, y] : p) {
        for(int i = 0; i < 8; ++i) {
            int cur_x = x + dx[i], cur_y = y + dy[i];
            if(cp(cur_x, cur_y, n, m)) {
                mp[cur_x][cur_y] = 0;
            }
        }
    }

    bfs();

    int mn = mx;
    for(int i = 0; i < n; ++i) {
        mn = min(mn, dist[i][m - 1]);
    }

    cout << ((mn < mx) ? mn : -1) << '\n';

    return 0;
}