Submission

Score: 100

User: konthaina_TH

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

Language: cpp

Time: 0.097 second

Submitted On: 2026-03-07 10:56:05

#include <bits/stdc++.h>

using namespace std;

struct Node {
    int r,c,dist;
};

int main() {
    int n,m;
    cin >> n >> m;
    vector<vector<int>>base(n+2,vector<int>(m+2,1));

    for (int i=1;i<=n;i++) {
        for (int j=1;j<=m;j++) {
            int x;
            cin >> x;
            if (x == 0) {
                base[i][j] = 0;
                base[i][j-1] = 0;
                base[i][j+1] = 0;
                base[i-1][j] = 0;
                base[i+1][j] = 0;
                base[i+1][j+1] = 0;
                base[i-1][j-1] = 0;
                base[i+1][j-1] = 0;
                base[i-1][j+1] = 0;
            }
        }
    }
    queue<Node> q;
    vector<vector<bool>> visited(n+1,vector<bool>(m+1,false));

    for (int i=1;i<=n;i++) {
        if (base[i][1] == 1) {
            q.push({i,1,1});
            visited[i][1] = true;
        }
    }
    int dr[] = {-1,1,0,0};
    int dc[] = {0,0,-1,1};

    while (!q.empty()) {
        Node curr = q.front();
        q.pop();

        if (curr.c == m) {
            cout << curr.dist << "\n";
            return 0;
        }

        for (int i=0;i<4;i++) {
            int nr = curr.r + dr[i];
            int nc = curr.c + dc[i];

            if (nr >= 1 and nr <= n and nc >= 1 and nc <= m and !visited[nr][nc] and base[nr][nc] == 1) {
                visited[nr][nc] = true;
                q.push({nr,nc,curr.dist + 1});
            }
        }
    }
    cout << "-1";
    return 0;

}