Submission

Score: 0

User: sorrkub

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

Language: cpp

Time: 0.095 second

Submitted On: 2026-02-08 21:18:06

#include<bits/stdc++.h>
using namespace std;
int dx[8] = {0,0,-1,1,-1,1,-1,1} , dy[8] = {1,-1,0,0,1,-1,1,-1};

int main(){
    int n,m;
    cin>>n>>m;
    vector<vector<bool>> vec(n,vector<bool> (m,true));
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            int a;
            cin>>a;
            if(a == 0){
                vec[i][j] = false;
                for(int x=0;x<8;x++){
                    int rr = i+dy[x] , cc = j + dx[x];
                    if(rr >= 0 && rr<n && cc>=0 && cc <m){
                        vec[rr][cc] = false;
                    }
                }
            }
        }
    }
    const int inf = 1e9+7;
    vector<vector<int>> vis(n,vector<int> (m,inf));
    queue<pair<int,int>> que;
    for(int i=0;i<n;i++){
        if(vec[i][0]){
            que.push({i,0});
            vis[i][0] = 0;
        }
    }
    while(!que.empty()){
        auto [r,c] = que.front();
        que.pop();
        for(int i=0;i<4;i++){
            int rr = r + dy[i],cc = c+dx[i];
            if(rr >=0 && rr<n && cc>=0 && cc<m && vec[rr][cc] && vis[rr][cc] > vis[r][c]+1){
                vis[rr][cc] = vis[r][c] + 1;
                //vec[rr][cc] = false;
                que.push({rr,cc});
            } 
        }
    }
    int minn =inf;
    for(int i=0;i<n;i++){
        // for(int j=0;j<m;j++){
        //     cout<<vis[i][j]<<" ";
        // }
        // cout<<'\n';
        minn = std::min(minn, vis[i][m-1]);
    }
    if(minn == inf){
        cout<<"-1";
    return 0;
    }
    cout<<minn+1;
}

/*
                   _ooOoo_
                  o8888888o
                  88" . "88
                  (| -_- |)
                  O\  =  /O
               ____/`---'\____
             .'  \|     |//  `.
            /  \|||  :  |||//  \
           /  _||||| -:- |||||-  \
           |   | \  -  /// |   |
           | \_|  ''\---/''  |   |
           \  .-\__  `-`  ___/-. /
         ___`. .'  /--.--\  `. . __
      ."" '<  `.___\_<|>_/___.'  >'"".
     | | :  `- \`.;`\ _ /`;.`/ - ` : | |
     \  \ `-.   \_ __\ /__ _/   .-` /  /
======`-.____`-.___\_____/___.-`____.-'======
                   `=---='
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
              pass System Test!
*/