Submission

Score: 100

User: Hxluk.ka

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

Language: cpp

Time: 0.085 second

Submitted On: 2025-12-16 21:19:24

#include <iostream>
#include <queue>
#include <utility>
using namespace std;
int map[1003][1003], tmp, mn=1e7, m, n, dir8[8][2]={{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1}}, dir4[4][2]={{0,1},{1,0},{-1,0},{0,-1}}, dist[1005][1005];
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>>map[i][j];
        if (map[i][j] == 0) q.push({i, j});
    }

    while (!q.empty()) {
        auto [x,y] = q.front();
        q.pop();
        for (int k=0; k<8; k++) map[x+dir8[k][0]][y+dir8[k][1]]=0;
    }

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

    for (int i=1; i<=n; i++) if (map[i][1]) {q.push({i, 1}); dist[i][1]=1;}
    while (!q.empty()) {
        auto [curr_i, curr_j] = q.front();
        q.pop();

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

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

    cout << -1;
    return 0;
}