Submission

Score: 100

User: Hxluk.ka

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

Language: cpp

Time: 0.073 second

Submitted On: 2025-12-18 21:29:43

#include <iostream>
#include <vector>
#include <queue>
#include <utility>
using namespace std;
int dir[8][2] = {{0,1},{1,0},{-1,0},{0,-1},{1,-1},{1,1},{-1,-1},{-1,1}};
const int nx = 1003;
int mp[nx][nx], n, m, dist[nx][nx];
queue<pair<int,int>> q;
int main() {
    cin.tie(0)->sync_with_stdio(0);

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

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

        for (int k=0; k<8; k++) {
            mp[curr_i+dir[k][0]][curr_j+dir[k][1]]=0;
        }
    }

    // for (int i=1; i<=n; i++) {
    //     for (int j=1; j<=m; j++) {
    //         cout << mp[i][j] << ' ';
    //     }
    //     cout << '\n';
    // }

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

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

        for (int k=0; k<4; k++) {
            int new_i = curr_i+dir[k][0], new_j = curr_j+dir[k][1];
            if (!mp[new_i][new_j] || dist[curr_i][curr_j]+1 < dist[new_i][new_j]) continue;
            if (new_j==m) {
                cout << dist[curr_i][curr_j]+1;
                return 0;
            }
            dist[new_i][new_j] = dist[curr_i][curr_j] + 1;
            mp[new_i][new_j] = 0;
            q.push({new_i, new_j});
        }
    }

    // cout << '\n';
    // for (int i=1; i<=n; i++) {
    //     for (int j=1; j<=m; j++) {
    //         cout << dist[i][j] << ' ';
    //     }
    //     cout << '\n';
    // }
    cout << -1;
}