Submission

Score: 100

User: Neozaawwman1

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

Language: cpp

Time: 0.169 second

Submitted On: 2026-01-20 23:47:13

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

int N,M;
int dx8[8]={-1,0,0,1,-1,-1,1,1};
int dy8[8]={0,-1,1,0,1,-1,1,-1};
int dx4[4]={-1,0,0,1};
int dy4[4]={0,-1,1,0};

int ed[1005][1005];
int block[1005][1005];
int dista[1005][1005];

void mark(int y, int x){
    for(int i=0;i<8;i++){
        int ny=y+dy8[i];
        int nx=x+dx8[i];
        if(ny<1 || nx<1 || ny>N || nx>M) continue;
        block[ny][nx]=1;
    }
}

int main(){
    cin>>N>>M;
    for(int i=1;i<=N;i++){
        for(int j=1;j<=M;j++){
            cin>>ed[i][j];
        }
    }

    // mark ช่องอันตราย
    for(int i=1;i<=N;i++){
        for(int j=1;j<=M;j++){
            if(ed[i][j]==0){
                block[i][j]=1;
                mark(i,j);
            }
        }
    }

    queue<pair<int,int>> q;

    // เริ่มจากคอลัมน์ซ้าย
    for(int i=1;i<=N;i++){
        if(!block[i][1]){
            dista[i][1]=1;
            q.push({i,1});
        }
    }

    while(!q.empty()){
        auto [y,x]=q.front(); q.pop();
        for(int i=0;i<4;i++){
            int ny=y+dy4[i];
            int nx=x+dx4[i];
            if(ny<1 || nx<1 || ny>N || nx>M) continue;
            if(block[ny][nx] || dista[ny][nx]) continue;
            dista[ny][nx]=dista[y][x]+1;
            q.push({ny,nx});
        }
    }

    int ans=1e9;
    for(int i=1;i<=N;i++){
        if(dista[i][M]) ans=min(ans,dista[i][M]);
    }

    if(ans==1e9) cout<<-1;
    else cout<<ans;
}