Submission

Score: 0

User: Shangbin

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

Language: cpp

Time: 0.003 second

Submitted On: 2025-12-07 16:53:21

#include <bits/stdc++.h>

using namespace std;
#define int long long
#define pii pair<int, int> 

int m, n;
int mat[1005][1005], dist[1005][1005];
queue<pii> q;
pii dir[4] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

signed main(){
    cin >> n >> m;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            cin >> mat[i][j];
        }
    }
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            if (mat[i][j] == 0){
                for (int x = i-1; x <= i+1; x++)
                    for (int y = j-1; y <= j+1; y++) 
                        if (mat[x][y] != 0) mat[x][y] = 2;
            }
        }
    }
    for (int i = 1; i <= n; i++){
        if (mat[i][1] == 1){
            q.push({i, 1});
        }
    }
    while (!q.empty()){
        auto cur_node = q.front();
        q.pop();
        if (cur_node.second == m){
            cout << dist[cur_node.first][m] + 1;
            return 0;
        }
        for (int i = 0; i < 3; i++){
            int next_y = cur_node.first + dir[i].first;
            int next_x = cur_node.second + dir[i].second;
            if (mat[next_y][next_x] == 1){
                q.push({next_y, next_x});
                dist[next_y][next_x] = dist[cur_node.first][cur_node.second] + 1;
            }
        }
    }
    cout << -1;
}