Submission

Score: 0

User: tnka4_

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

Language: cpp

Time: 0.003 second

Submitted On: 2026-03-20 00:34:00

#include <iostream>
#include <vector>
#include <utility>
#include <climits>
using namespace std;

#define ll long long

ll y, x;
vector<pair<ll, ll>> dir = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};

bool isInside(ll i, ll j) {
    if (i >= 0 && i < y && j >= 0 && j < x) return true;
    return false;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    ll a;
    cin >> y >> x;
    vector<vector<ll>> grid(y, vector<ll>(x, 1));
    for (ll i=0; i<y; i++) {
        for (ll j=0; j<x; j++) {
            cin >> a;
            if (grid[i][j] == -1) continue;
            if (a == 0) {
                for (ll m=-1; m<=1; m++) {
                    for (ll n=-1; n<=1; n++) {
                        if (!isInside(i+m, j+n)) continue;
                        grid[i+m][j+n] = -1;
                    }
                }
            } else {
                if (j == 0 && grid[i][j] != -1) {
                    grid[i][j] = 1;
                    continue;
                }
                grid[i][j] = 0;
            }
        }
    }
    ll leastDist = 1e10;
    for (ll j=1; j<x; j++) {
        for (ll i=0; i<y; i++) {
            if (grid[i][j] == -1) continue;
            ll least = LLONG_MAX;
            for (auto &[dy, dx] : dir) {
                ll ny = i + dy;
                ll nx = j + dx;
                if (isInside(ny, nx) && grid[ny][nx] > 0) {
                    least = min(least, grid[ny][nx]);
                }
            }
            grid[i][j] = 1 + least;
            if (j == x-1) {
                leastDist = min(leastDist, grid[i][j]);
            }
        }
        for (ll i=y-1; i>=0; i--) {
            if (grid[i][j] >= -1) continue;
            ll least = LLONG_MAX;
            for (auto &[dy, dx] : dir) {
                ll ny = i + dy;
                ll nx = j + dx;
                if (isInside(ny, nx) && grid[ny][nx] > 0) {
                    least = min(least, grid[ny][nx]);
                }
            }
            grid[i][j] = 1 + least;
            if (j == x-1) {
                leastDist = min(leastDist, grid[i][j]);
            }
        }
    }
    // for (ll i=0; i<y; i++) {
    //     for (ll j=0; j<x; j++) {
    //         cout << grid[i][j] << "\t";
    //     }
    //     cout << endl;
    // }
    if (leastDist == 1e10 || leastDist == 0) {
        cout << -1;
        return 0;
    }
    cout << leastDist;
}