Author: lvvj
Date: 20250823
tag: 广度优先搜索
link: https://www.luogu.com.cn/problem/P1162

题目描述

link

分析

略

参考代码

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

const int N = 35;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
int g[N][N], n;

void bfs(int x, int y, int tag) {
    queue<pair<int, int>> q;
    q.push({x, y});
    g[x][y] = tag;

    while (q.size()) {
        auto h = q.front();
        q.pop();
        int x = h.first, y = h.second;

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx < 1 || nx > n || ny < 1 || ny > n) continue;
            if (g[nx][ny] != 0) continue;
            q.push({nx, ny});
            g[nx][ny] = tag;
        }
    }
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> g[i][j];
        }
    }

    for (int i = 1; i <= n; i++) {
        if (g[1][i] == 0) bfs(1, i, 3);
        if (g[n][i] == 0) bfs(n, i, 3);
    }

    for (int i = 2; i < n; i++) {
        if (g[i][1] == 0) bfs(i, 1, 3);
        if (g[i][n] == 0) bfs(i, n, 3);
    }

    for (int i = 2; i < n; i++) {
        for (int j = 2; j < n; j++) {
            if (g[i][j] == 0) {
                bfs(i, j, 2);
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cout << (g[i][j] == 3 ? 0 : g[i][j]) << " ";
        }
        cout << endl;
    }

    return 0;
}