Submission

Score: 0

User: Dormon

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

Language: cpp

Time: 0.100 second

Submitted On: 2025-05-29 14:15:28

#include <bits/stdc++.h>

using namespace std;
using pii = pair<int, int>;

vector<pii> dir4 = {{-1, 0}, {0, 1}, {1, 0}, {0, 1}};
vector<pii> dir8 = {{-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, 1}, {-1, -1}};

int main() 
{
    int n, m;
    cin >> n >> m;
    vector<vector<int>> grid(n + 2, vector<int>(m + 2, -1));
    vector<pii> bomb;
    for (int i = 1;i <= n;i++)
        for (int j = 1;j <= m;j++){
            cin >> grid[i][j];
            if (grid[i][j] == 0)
                bomb.push_back({i, j});
        }

    for (auto [i, j]:bomb)
        for (auto [di, dj]:dir8)
            grid[i + di][j + dj] = 0;

    auto invalid = [&](int i, int j) -> bool {
        return i < 1 || i > n || j < 1 || j > m || grid[i][j] == 0;
    };
    
    struct A {
        int i, j, w;
    };
    queue<A> q;
    for (int i = 1;i <= n;i++)
        if (grid[i][1])
            q.push({i, 1, 1});
            
    while (!q.empty()){
        auto [i, j, w] = q.front(); q.pop();
        if (grid[i][j] == 0) continue;
        grid[i][j] = 0;
        if (j == m){
            cout << w << '\n';
            return 0;
        }
        for (auto [di, dj]:dir4)
            if (!invalid(i + di, j + dj))
                q.push({i + di, j + dj, w + 1});
    }
    cout << "-1";
    return 0;
}