Submission

Score: 100

User: krittaphot

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

Language: cpp

Time: 0.100 second

Submitted On: 2026-03-07 11:52:06

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

int dx[8] = {1,1,1,0,0,-1,-1,-1};
int dy[8] = {1,0,-1,1,-1,1,0,-1};
int DX[4] = {1,0,-1,0};
int DY[4] = {0,1,0,-1};

int main(){
    int n,m;
    cin >> n >> m;
    vector<vector<int>> mp(n,vector<int>(m));
    vector<vector<int>> dist(n,vector<int>(m,INT_MAX));
    vector<vector<int>> check(n,vector<int>(m,1));
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin >> mp[i][j];
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(mp[i][j] == 0){
                check[i][j] = 0;
                for(int k=0;k<8;k++){
                    int x = i + dx[k];
                    int y = j + dy[k];
                    if(x >= 0 && x < n && y >= 0 && y < m){
                        if(mp[x][y] == 1){
                            check[x][y] = 0;
                        }
                    }
                }
            }
        }
    }
    
    // for(int i=0;i<n;i++){
    //     for(int j=0;j<m;j++){
    //         cout << check[i][j] << " ";
    //     }
    //     cout << endl;
    // }

    for(int i = 0;i<n;i++){
        if(check[i][0] == 1){
            dist[i][0] = 1;
        }
    }

    queue<pair<int,int>> q;
    for(int i = 0;i<n;i++){
        if(check[i][0] == 1){
            q.push({i,0});
        }
    }
    while(!q.empty()){
        auto cur = q.front();
        q.pop();
        int x = cur.first;
        int y = cur.second;
        for(int k=0;k<4;k++){
            int nx = x + DX[k];
            int ny = y + DY[k];
            if(nx >= 0 && nx < n && ny >= 0 && ny < m){
                if(check[nx][ny] == 1 && dist[nx][ny] > dist[x][y] + 1){
                    dist[nx][ny] = dist[x][y] + 1;
                    q.push({nx,ny});
                }
            }
        }
    }

    int ans = INT_MAX;
    for(int i=0;i<n;i++){
        if(check[i][m-1] == 1){
            ans = min(ans,dist[i][m-1]);
        }
    }

    if(ans == INT_MAX){
        cout << -1 << endl;
    }else
        cout << ans << endl;
    
}