Submission

Score: 100

User: skibididopdop

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

Language: cpp

Time: 0.052 second

Submitted On: 2026-03-15 15:55:45

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

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,m;
    cin>>n>>m;
    int dx1[]={-1,0,1,0,-1,-1,1,1};
    int dy1[]={0,-1,0,1,1,-1,1,-1};
    int dx2[]={-1,0,1,0};
    int dy2[]={0,-1,0,1};
    vector <vector<int>> v(n,vector <int>(m));
    for (int i=0;i<n;i++){
        for (int j=0;j<m;j++){
            cin>>v[i][j];
        }
    }
    vector <vector<int>> mine(n,vector <int>(m,1));;
    for (int i=0;i<n;i++){
        for (int j=0;j<m;j++){
            if (v[i][j]==0){
                mine[i][j]=0;
                for (int k=0;k<8;k++){
                    int uu=i+dx1[k];
                    int vv=j+dy1[k];
                    if (uu>=0&&vv>=0&&uu<n&&vv<m) mine[uu][vv]=0;
                }
            }
        }
    }
    queue <pair<int,int>> q;
    vector <vector<int>> dist(n,vector <int>(m,INT_MAX));;
    for (int i=0;i<n;i++){
        if (mine[i][0]!=0){
            q.push({i,0});
            mine[i][0]=0;
            dist[i][0]=1;
        }
    }
    /*
    for (int i=0;i<n;i++){
        for (int j=0;j<m;j++){
            cout<<mine[i][j]<<" ";
        }
        cout<<"\n";
    }
    */
    while (!q.empty()){
        int u=q.front().first;
        int v=q.front().second;
        q.pop();
        //cout<<u<<" "<<v<<"\n";
        for(int i=0;i<4;i++){
            int uu=u+dx2[i];
            int vv=v+dy2[i];
            //cout<<uu<<" "<<vv<<"\n"<<"///";
            if (uu>=0&&vv>=0&&uu<n&&vv<m&&mine[uu][vv]==1&&dist[uu][vv]>dist[u][v]+1){
                q.push({uu,vv});
                mine[uu][vv]=0;
                dist[uu][vv]=dist[u][v]+1;
            }
        }
    }
    /*
    for (int i=0;i<n;i++){
            for (int j=0;j<m;j++){
                cout<<dist[i][j]<<" ";
            }
            cout<<"\n";
        }
        */
    int check=0;
    int mn=INT_MAX;
    for (int i=0;i<n;i++){
        if (dist[i][m-1]!=INT_MAX&&dist[i][m-1]<mn){
            mn=dist[i][m-1];
            check=1;
        }
    }
    if (check==0){
        cout<<-1;
    }

    else{
        cout<<mn;
    }
}