Submission

Score: 100

User: meme_boi2

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

Language: cpp

Time: 0.104 second

Submitted On: 2025-11-02 22:04:52

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define tii tuple<int,int,int>
int dx[] = {1,0,-1,0}, dy[] = {0,1,0,-1};
vector<pii> d = {{1,0},{1,-1},{-1,0},{1,1},{0,1},{-1,1},{0,-1},{-1,-1}};
int mat[1002][1002];
vector<vector<int>> dist(1002,vector<int>(1002,INT_MAX));
priority_queue<tii,vector<tii>,greater<tii>> pq;
int32_t main(){
    cin.tie(nullptr)->sync_with_stdio(0);
    int m, n;
    cin >> m >> n;
    
    stack<pii> st;
    for(int i =1; i <= m; i++){
        for(int j =1; j <= n; j++){
            cin >> mat[i][j];
            if(mat[i][j] == 0){
                st.push({i,j});
            }
        }
    }
    while(!st.empty()){
        auto [r,c] = st.top();
        st.pop();
        for(int k = 0; k < 8; k++){
            mat[r+d[k].first][c+d[k].second] = 0;
        }
    }
  //  pq.push({1,1,1});
   // dist[1][1] = 1;
    for(int i = 1; i <= m; i++){
        if(mat[i][1] != 0){
            dist[i][1] = 1;
            pq.push({1,i,1});
            //break;
        }
    }
    while(!pq.empty()){
        auto [w,r,c] = pq.top();
        pq.pop();
      //  cout << w << ' ' << r << ' ' << c << '\n';
        if(w > dist[r][c]) {  continue;}
        if(r > 1000 || c > 1000 || r < 1 || c < 1) { continue;}
        for(int k = 0; k < 4; k++){
            if(w + 1 < dist[r+dx[k]][c+dy[k]] && mat[r+dx[k]][c+dy[k]] != 0){
                pq.push({dist[r+dx[k]][c+dy[k]]= w+1,r+dx[k],c+dy[k]});
                //cout << "huh\n";
            }
        }
        //cout << "kungaroo";
    }
    int ans = INT_MAX;
    for(int i = 1; i <= m && false ; i++){
        for(int j = 1; j <= n; j++){
            cout << dist[i][j] << ' ';
        }
        cout << '\n';
    }
    for(int i = 1; i <= m; i++){
        
                ans = min(ans,dist[i][n]);
          
    }
    if(ans == INT_MAX) cout << -1;
    else cout << ans;
}