Submission

Score: 0

User: Neozaawwman1

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

Language: cpp

Time: 0.087 second

Submitted On: 2026-01-20 23:38:16

#include <bits/stdc++.h>
using namespace std;
int N,M;
int xx[8]={-1,0,0,1,-1,-1,1,1};
int yy[8]={0,-1,1,0,1,-1,1,-1};
int ed[1005][1005];
int vs[1005][1005];
int ct[1005][1005];
queue<tuple<int,int,int>> q;
void mark(int y, int x){
    for(int i=0; i<8; i++){
        int nx=x+xx[i];
        int ny=y+yy[i];
        if(nx<1 || ny<1 || nx>N || ny>M)continue;
        if(vs[ny][nx])continue;
        vs[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];
        }
    }
    for(int i=1; i<=N; i++){
        for(int j=1; j<=M; j++){
            if(ed[i][j]==0){
                 vs[i][j]=1;
                 mark(i,j);
                }
            }
        }
    
    for(int i=1; i<=N; i++){
        if(ed[i][0]=1){
            q.push({i,0,1});
        }
    }
    while(!q.empty()){
        int x,y,t;
        tie(y,x,t)=q.front();
        q.pop();
        if(vs[y][x])continue;
        vs[y][x]=1;
        for(int i=0; i<4; i++){
            int nx=x+xx[i];
            int ny=y+yy[i];
            if(nx<1 || ny<1 || nx>N || ny>M)continue;
            if(vs[ny][nx])continue;
            ct[ny][nx]=t;
            q.push({ny,nx,t+1});
        }
    }
    int mn=100005;
    for(int i=1; i<=N; i++){
        if(mn>ct[i][M] && ct[i][M]!=0)mn=ct[i][M];
    }
    if(mn==100005)cout<<-1<<endl;
    else cout<<mn<<endl;
    return 0;
}