Submission

Score: 100

User: Gump2011

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

Language: cpp

Time: 0.062 second

Submitted On: 2026-03-08 17:49:17

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int N, M;
    cin >> N >> M;

    vector<vector<int>> a(N, vector<int>(M));
    vector<vector<bool>> safe(N, vector<bool>(M, true));
    vector<vector<int>> dist(N, vector<int>(M, -1));

    for(int i=0;i<N;i++)
        for(int j=0;j<M;j++)
            cin >> a[i][j];

    // mark ช่องรอบระเบิดไม่ปลอดภัย
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            if(a[i][j]==0){
                for(int di=-1; di<=1; di++){
                    for(int dj=-1; dj<=1; dj++){
                        int ni = i + di, nj = j + dj;
                        if(ni>=0 && ni<N && nj>=0 && nj<M)
                            safe[ni][nj] = false;
                    }
                }
            }
        }
    }

    // BFS
    queue<pair<int,int>> q;
    for(int i=0;i<N;i++){
        if(safe[i][0]){
            q.push(make_pair(i,0));
            dist[i][0] = 1; // เริ่มนับช่องแรกด้วย
        }
    }

    int dx[4] = {1,-1,0,0};
    int dy[4] = {0,0,1,-1};

    while(!q.empty()){
        pair<int,int> cur = q.front(); q.pop();
        int x = cur.first;
        int y = cur.second;

        for(int k=0;k<4;k++){
            int nx = x + dx[k], ny = y + dy[k];
            if(nx>=0 && nx<N && ny>=0 && ny<M && safe[nx][ny] && dist[nx][ny]==-1){
                dist[nx][ny] = dist[x][y]+1;
                q.push(make_pair(nx,ny));
            }
        }
    }

    int ans = INT_MAX;
    for(int i=0;i<N;i++){
        if(dist[i][M-1]!=-1) ans = min(ans, dist[i][M-1]);
    }

    if(ans==INT_MAX) cout << -1 << "\n";
    else cout << ans << "\n";

    return 0;
}