Submission

Score: 100

User: Regent

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

Language: cpp

Time: 0.065 second

Submitted On: 2026-03-05 20:57:05

#include<bits/stdc++.h>
#define Kana ios::sync_with_stdio(false);cin.tie(nullptr);
using namespace std;

int n,m;
int dx8[] = {-1,-1,-1,0,0,1,1,1};
int dy8[] = {-1,0,1,-1,1,-1,0,1};
int dx4[] = {0,0,1,-1};
int dy4[] = {1,-1,0,0};

int main(){
    Kana;

    cin >> n >> m;
    vector<vector<int>> grid(n,vector<int>(m));
    vector<vector<int>> bad(n,vector<int>(m,0));
    vector<vector<int>> dist(n,vector<int>(m,-1));

    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            cin >> grid[i][j];

    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(grid[i][j]==0){
                bad[i][j]=1;
                for(int k=0;k<8;k++){
                    int ni=i+dx8[k];
                    int nj=j+dy8[k];
                    if(ni>=0 && nj>=0 && ni<n && nj<m)
                        bad[ni][nj]=1;
                }
            }
        }
    }

    queue<pair<int,int>> q;

    for(int i=0;i<n;i++){
        if(!bad[i][0]){
            q.push({i,0});
            dist[i][0]=1;
        }
    }

    while(!q.empty()){
        auto [x,y]=q.front();
        q.pop();

        for(int k=0;k<4;k++){
            int nx=x+dx4[k];
            int ny=y+dy4[k];

            if(nx>=0 && ny>=0 && nx<n && ny<m){
                if(!bad[nx][ny] && dist[nx][ny]==-1){
                    dist[nx][ny]=dist[x][y]+1;
                    q.push({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;
    else cout<<ans;
}