Submission

Score: 0

User: Hxluk.ka

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

Language: cpp

Time: 0.070 second

Submitted On: 2025-12-16 20:56:57

#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}}, vs[1005][1005], 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) {
            vs[i][j]=1;
            for (int k=0; k<8; k++) vs[i+dir8[k][0]][j+dir8[k][1]]=1;
        }
    }

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

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

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

        for (int k=0; k<4; k++) {
            int new_i = curr_i+dir4[k][0], new_j = curr_j+dir4[k][1];
            if (new_j == m) {cout << dist[curr_i][curr_j]+1; return 0;}
            if (new_i <= 0 || new_i > n || new_j <= 0 || new_j > n || vs[new_i][new_j]) continue;
            q.push({new_i, new_j});
            if (dist[new_i][new_j]==0) 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';
    // }

    for (int i=1; i<=n; i++) if (mn>dist[i][n]&&dist[i][n]!=0) mn=dist[i][n];
    if (mn == 1e7) cout << -1;
    else cout << mn;
}