Submission

Score: 0

User: Dormon

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

Language: cpp

Time: 0.092 second

Submitted On: 2025-05-29 14:05:19

#include <bits/stdc++.h>

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

vector<pair<int, int>> dir = {{-1, 0}, {0, 1}, {1, 0}, {0, 1}};

int main() 
{
    int n, m;
    cin >> n >> m;
    vector<vector<int>> grid(n + 2, vector<int>(m + 2, 10));
    
    for (int i = 1;i <= n;i++)
        for (int j = 1;j <= m;j++){
            int t;
            cin >> t;
            if (t == 0){
                for (int di = -1;di <= 1;di++)
                    for (int dj = -1;dj <= 1;dj++)
                        grid[i + di][j + dj] = 0;
            }
            else
                grid[i][j] = min(grid[i][j], t);
        }
        
    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]:dir)
            if (!invalid(i + di, j + dj))
                q.push({i + di, j + dj, w + 1});
    }
    cout << "-1";
    return 0;
}