Submission

Score: 0

User: SnowAveNode

Problemset: fireball

Language: cpp

Time: 0.004 second

Submitted On: 2026-03-01 20:21:00

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

const int nx = 1005;
int vis[nx][nx] = {0}, dist[nx][nx] = {0};

int dmy[] = {-1, 1, -1, 1, -1, 1, 0, 0}, dmx[] = {0, 0, -1, 1, 1, -1, -1, 1};
int dy[] = {-1, 1, 0, 0}, dx[] = {0, 0, -1, 1};

int main() {

    ios::sync_with_stdio(false); cin.tie(nullptr);

    int n, m; cin >> n >> m; int ans = INT_MAX;
    vector<vector<int>> mp(n, vector<int>(m));

    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) {
            for(int k = 0; k < 8; k++) {
                int ny = i + dmy[k];
                int nx = j + dmx[k];
                if(ny < 0 || ny >= n || nx < 0 || nx >= m) continue;
                if(mp[ny][nx] == 1) mp[ny][nx] = 2;
            }
        }
    }

    queue<pair<int, int>> q;
    for(int i = 0; i < n; i++) if(mp[i][0] == 1) {dist[i][0] = 1; vis[i][0] = 1; q.push({i, 0});};
    while(!q.empty()) {
        auto [y, x] = q.front(); q.pop();
        for(int k = 0; k < 4; k++) {
            int ny = y + dy[k];
            int nx = x + dx[k];
            if(ny < 0 || ny >= n || nx < 0 || nx >= m) continue;
            if(mp[ny][nx] != 1 || vis[ny][nx]) continue;
            vis[ny][nx] = 1; dist[ny][nx] = dist[y][x] + 1; q.push({ny, nx});
        }
    }

    //for(int i = 0; i < n; i++){for(int j = 0; j < m; j++) {cout << dist[i][j] << " ";} cout << endl;}
    for(int i = 0; i < n; i++) if(vis[i][m-1]) ans = min(ans, dist[i][m-1]);
    if(ans == INT_MAX) cout << -1; else cout << ans << endl;

    return 0;
}