Submission

Score: 0

User: raidina

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

Language: cpp

Time: 0.088 second

Submitted On: 2026-03-06 21:52:44

#include <iostream>
#include <queue>
#include <utility>
#include <limits.h>
using namespace std;

const int N = 1002;
int n,m;
int arr[N][N],dp[N][N];
bool visited[N][N];
queue<pair<int,int>> q;

int main(){
    cin >> n >> m;
    for(int i = 1;i<=n;i++)
        for(int j = 1;j<=m;j++)
            cin >> arr[i][j];

    for(int i = 1;i<=n;i++)
        for(int j = 1;j<=m;j++)
            dp[i][j]= INT_MAX;
        
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=m;j++){
            if(arr[i][j]== 0 && !visited[i][j]){
                for(int a = -1;a<=1;a++){
                    for(int b = -1;b<=1;b++){
                        if(visited[i+a][j+b])continue;
                        arr[i+a][j+b]=0;
                        visited[i+a][j+b]=true;
                    }
                }   
            }
        }
    }

    // for(int i = 1;i<=n;i++){
    //     for(int j = 1;j<=m;j++)
    //         cout <<  arr[i][j]<<' ';
    //     cout << '\n';
    // }

    for(int i = 1;i<=n;i++){
        // for(int k = 1;k<=n;k++){
        //     for(int j = 1;j<=m;j++){
        //         if(arr[i][j]==1)visited[k][j]=false;
        //     }
        // }
        q.push({i,1});
        dp[i][1]=1;
       
    }
     while(!q.empty()){
            int x = q.front().first;
            int y = q.front().second;

            q.pop();
            if(visited[x][y])continue;
            visited[x][y] = true;
            int d1[4]={-1,1,0,0};
            int d2[4]={0,0,-1,1};

            for(int j = 0;j<4;j++){
                int nx = x+d1[j];
                int ny = y+d2[j];
                if(nx<1 || nx >n || ny<1||nx>n)continue;
                if(!visited[nx][ny] && arr[nx][ny]==1){
                    if(dp[x][y]+1 < dp[nx][ny]){
                        dp[nx][ny]=dp[x][y]+1;
                        q.push({nx,ny});
                    }
                    
                }
            }

    }
    int ans=INT_MAX;
    for(int i = 1;i<=n;i++){
        ans=min(dp[i][n],ans);
    }
    if(ans != INT_MAX)cout << ans;
    else cout << -1;


        

    
}