Submission

Score: 100

User: njoop

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

Language: cpp

Time: 0.093 second

Submitted On: 2025-05-20 18:47:58

#include <bits/stdc++.h>

using namespace std;

int dx[8] = {1, 0, -1, 0, 1, -1, 1, -1}, dy[8] = {0, 1, 0, -1, 1, -1, -1, 1};
int arr[1010][1010], dis[1010][1010], n, m;

queue<tuple<int, int, int>> q;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    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++) {
            if(arr[i][j] == 0) {
                for(int k=0; k<8; k++) {
                    if(arr[i+dx[k]][j+dy[k]] != 0) {
                        arr[i+dx[k]][j+dy[k]] = 2;
                    }
                }
            }
            dis[i][j] = 1e9;
        }
    }
    for(int i=1; i<=n; i++) {
        if(arr[i][1] != 1) continue;
        dis[i][1] = 1;
        q.push({1, i, 1});
    }
    while(q.size()) {
        int cd = get<0>(q.front()), cx = get<1>(q.front()), cy = get<2>(q.front());
        q.pop();
        if(dis[cx][cy] < cd) continue; 
        for(int i=0; i<4; i++) {
            int nx = cx+dx[i], ny = cy+dy[i];
            if(nx < 1 || nx > n || ny < 1 || ny > m) continue;
            if(arr[nx][ny] == 1 && dis[nx][ny] > cd+1) {
                dis[nx][ny] = cd+1;
                q.push({cd+1, nx, ny});
            } 
        }
    }
    int ans = 1e9;
    for(int i=1; i<=n; i++) {
        ans = min(ans, dis[i][m]);
    }
    if(ans == 1e9) cout << -1;
    else cout << ans;
    return 0;
}