Submission

Score: 100

User: august

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

Language: cpp

Time: 0.058 second

Submitted On: 2026-03-10 21:49:25

#include <bits/stdc++.h>
using namespace std;
#define pi pair<int,int>

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n,m;
    cin>> n>> m;

    vector<vector<int>> in(n+1, vector<int>(m+1)), dist(n+1, vector<int>(m+1, -1)), g(n+1, vector<int>(m+1, 1));
    for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) cin>> in[i][j];

    int di[8] = {-1, 0, 1, 0, -1, 1, 1, -1}, dj[8] = {0, 1, 0, -1, 1, 1, -1, -1};

    for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) if (in[i][j] == 0) {
        g[i][j]=0;
        for (int e=0; e<8; e++) {
            int ni=i+di[e], nj=j+dj[e];
            if (ni<1 || ni>n || nj<1 || nj>m) continue;
            g[ni][nj] = 0;
        }
    }

    queue<pi> q;
    for (int i=1; i<=n; i++) if (g[i][1]) q.push({i,1}), dist[i][1] = 1;

    while (!q.empty()) {
        int i=q.front().first, j=q.front().second;
        q.pop();

        for (int e=0; e<4; e++) {
            int ni=i+di[e], nj=j+dj[e];
            if (ni<1 || ni>n || nj<1 || nj>m || dist[ni][nj] != -1 || !g[ni][nj]) continue;
            dist[ni][nj] = dist[i][j] + 1;
            q.push({ni,nj});
        }
    }
    int ans = INT_MAX;
    for (int i=1; i<=n; i++) if (dist[i][m] != -1) ans = min(ans, dist[i][m]);
    
    /*for (int i=1; i<=n; i++) {
        for (int j=1; j<=m; j++) cout<< dist[i][j]<< ' ';
        cout<< '\n';
    }*/
    cout<< (ans==INT_MAX ? -1 : ans);
}