Submission

Score: 100

User: devilpoohs

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

Language: cpp

Time: 0.075 second

Submitted On: 2026-03-05 21:27:03

#include<bits/stdc++.h>
using namespace std;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,m;
    cin>>n>>m;
    int walk[n][m];
    int dii[8]={-1,-1,-1,0,0,1,1,1};
    int dij[8]={-1,0,1,-1,1,-1,0,1};
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>walk[i][j];
        }
    }
    
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(walk[i][j]==0){
                for(int k=0;k<8;k++){
                    int ni=i+dii[k];
                    int nj=j+dij[k];
                    if(ni>=0 and ni<n and nj>=0 and nj<m and walk[ni][nj]!=0){
                        walk[ni][nj]=-1;
                    }
                }
            }
        }
    }
    // for(int i=0;i<n;i++){
    //     for(int j=0;j<m;j++){
    //         cout<<walk[i][j]<<' ';
    //     }
    //     cout<<'\n';
    // }
    queue<pair<pair<int,int>,int>> q;
    int di[4]={1,-1,0,0};
    int dj[4]={0,0,1,-1};
    for(int i=0;i<n;i++){
        if(walk[i][0]!=0 and walk[i][0]!=-1){
            q.push({{i,0},1});
        }
    }
    bool vis[n][m];
    memset(vis,false,sizeof(vis));
    while(!q.empty()){
        auto cur=q.front();
        q.pop();
        int curi=cur.first.first;
        int curj=cur.first.second;
        int curw=cur.second;
        if(vis[curi][curj] or walk[curi][curj]<=0) continue;
        vis[curi][curj]=true;
        if(curj==m-1){
            cout<<curw;
            return 0;
        }
        for(int i=0;i<4;i++){
            int ni=curi+di[i];
            int nj=curj+dj[i];
            if(ni>=0 and nj>=0 and ni<n and nj<m and walk[ni][nj]>0 ){
                q.push({{ni,nj},curw+1});
            }
        }
    }
    cout<<"-1";
    return 0;
}