Submission

Score: 0

User: ttttttttt

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

Language: cpp

Time: 0.004 second

Submitted On: 2025-12-07 14:55:06

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

void bomb(vector<vector<int>>& arr, int x, int y) {
    vector<pair<int,int>> idx = {
        {x+1,y}, {x-1,y}, {x,y+1},{x,y-1},
        {x+1,y+1},{x+1,y-1},{x-1,y+1},{x-1,y-1}
    };

    for (auto [xx, yy] : idx) {
        if (xx < 0 || xx >= arr.size()) continue;
        if (yy < 0 || yy >= arr[0].size()) continue;
        arr[xx][yy] = 0;
    }
}

void bfs_step(const vector<vector<int>>& arr,
              int x, int y,
              queue<pair<int,int>>& q,
              vector<vector<int>>& visited,
              vector<vector<int>>& dist) 
{
    vector<pair<int,int>> idx = {
        {x+1,y}, {x-1,y}, {x,y+1},{x,y-1},
        {x+1,y+1},{x+1,y-1},{x-1,y+1},{x-1,y-1}
    };

    for (auto [xx, yy] : idx) {
        if (xx < 0 || xx >= arr.size()) continue;
        if (yy < 0 || yy >= arr[0].size()) continue;
        if (!visited[xx][yy]) {
            if (arr[xx][yy] != 0)
                dist[xx][yy] = dist[x][y] + 1;
            visited[xx][yy] = true;
            q.push({xx, yy});
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;

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

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (arr[i][j] == 0)
                bomb(arr, i, j);

    queue<pair<int,int>> q;
    vector<vector<int>> dist(n, vector<int>(m, INT_MAX));
    vector<vector<int>> visited(n, vector<int>(m, false));

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

    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        bfs_step(arr, x, y, q, visited, dist);
    }

    int ans = INT_MAX;
    for (int i = 0; i < n; i++)
        ans = min(ans, dist[i][m-1]);

    cout << (ans == INT_MAX ? -1 : ans) << endl;
}