Submission

Score: 100

User: APNICHANAN

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

Language: cpp

Time: 0.067 second

Submitted On: 2026-03-06 15:34:45

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll a[1005][1005] , mini = 1e9 , d[1005][1005];
ll bx[8] = {1,1,1,0,0,-1,-1,-1} , by[8] = {1,0,-1,1,-1,1,0,-1} ;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n , m ; cin >> n >> m ;

    for (int i = 1 ; i <= n ; i++)
        for (int j = 1 ; j <= m ; j++){
            cin >> a[i][j] ;
            d[i][j] = 1e9 ;
        }

    for (int i = 1 ; i <= n ; i++)
        for (int j = 1 ; j <= m ; j++){
            if (a[i][j] == 0){
                for (int k =0 ; k < 8 ; k++){
                    if (i + by[k] < 1 || j + bx[k] < 1 || i + by[k] > n || j + bx[k] > m)
                    continue;
                    if (a[i + by[k]][j + bx[k]] != 0)
                        a[i + by[k]][j + bx[k]] = -1 ;
                }
            }
        }
    ll dx[4] = {0,0,1,-1} , dy[4] = {1,-1,0,0} ;

    queue<pair<ll,ll>> q ;
    for (int j = 1 ; j <= n ; j++){
    q.push({j,1}) ;
    d[j][1] = 1 ;
    }
    while (!q.empty()){
        ll ny = q.front().first , nx = q.front().second;
        q.pop() ;
        for (int i = 0 ; i < 4 ; i++){
            ll nxtx = nx + dx[i] , nxty = ny + dy[i] ;
            if (nxtx <= 0 || nxty <= 0 || nxtx > m || nxty > n || a[nxty][nxtx] <= 0)
                continue;
            if (d[nxty][nxtx] > d[ny][nx] + 1 ){
                d[nxty][nxtx] = d[ny][nx] + 1 ;
                q.push({nxty , nxtx}) ;
            }
        }
    }


    for (int j = 1 ; j <= n ; j++){
        mini = min(d[j][m] , mini) ;
    }

    if (mini == 1e9)
        cout << "-1\n" ;
    else
        cout << mini << "\n" ;
}