Untitled

mail@pastecode.io avatar
unknown
plain_text
2 months ago
1.8 kB
1
Indexable
Never
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m;
    cin >> n >> m;
    vector <vector <int>>grid(n, vector <int> (m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> grid[i][j];
        }
    }
    vector <vector <int>> vis(n, vector <int> (m, 1e9));
    queue <pair<int, int>> q;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (grid[i][j] == 2) {
                vis[i][j] = 0;
                q.push({i, j});
            }
        }
    }
    while (!q.empty()) {
        auto cur = q.front();
        q.pop();
        int i, j;
        i = cur.first;
        j = cur.second;
        if (i && grid[i - 1][j] != 0) {
            if (vis[i - 1][j] == 1e9) {
                vis[i - 1][j] = vis[i][j] + 1;
                q.push({i - 1, j});
            }
        }
        if (i + 1 < n && grid[i + 1][j] != 0) {
            if (vis[i + 1][j] == 1e9) {
                vis[i + 1][j] = vis[i][j] + 1;
                q.push({i + 1, j});
            }
        }
        if (j && grid[i][j - 1] != 0) {
            if (vis[i][j - 1] == 1e9) {
                vis[i][j - 1] = vis[i][j] + 1;
                q.push({i, j - 1});
            }
        }
        if (j + 1 < m && grid[i][j + 1] != 0) {
            if (vis[i][j + 1] == 1e9) {
                vis[i][j + 1] = vis[i][j] + 1;
                q.push({i, j + 1});
            }
        }
    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (grid[i][j] != 0) {
                ans = max(ans, vis[i][j]);
            }
        }
    }
    if (ans == 1e9)
        ans = -1;
    cout << ans;
}
Leave a Comment