算法题：填涂颜色

问题描述

由数字0组成的方阵中，有一任意形状闭合圈，闭合圈由数字1构成，围圈时只走上下左右4个方向。现要求把闭合圈内的所有空间都填写成2.例如：6×6 的方阵（n=6），涂色前和涂色后的方阵如下

0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 0 0 1
1 1 0 0 0 1
1 0 0 0 0 1
1 1 1 1 1 1

0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 2 2 1
1 1 2 2 2 1
1 2 2 2 2 1
1 1 1 1 1 1

输入格式

每组测试数据第一行一个整数n(1≤n≤30)
接下来n行，由0和1组成的n×n 的方阵。
方阵内只有一个闭合圈，圈内至少有一个0。

数之间以空格分隔 ， 注意行末不需要多余空格。

输出格式

已经填好数字2的完整方阵。

样例

输入

6
0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 0 0 1
1 1 0 0 0 1
1 0 0 0 0 1
1 1 1 1 1 1

输出

0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 2 2 1
1 1 2 2 2 1
1 2 2 2 2 1
1 1 1 1 1 1

数据范围

1≤n≤30

解决方案

思路

广度优先搜索

代码

#include <iostream>
#include <queue>

using namespace std;

int n;
int arr[35][35];
bool vis[35][35];

// 方向
int x[4] = {0, 0, -1, 1}, y[4] = {-1, 1, 0, 0};

int main() {
    cin >> n;

    //扩充一圈0 方便选出未被围圈的0
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            int t;
            cin >> t;
            arr[i][j] = t;
        }
    }

    queue<pair<int, int>> q;
    q.push({0, 0});

    while (!q.empty()) {
        pair<int, int> point = q.front();
        q.pop();
        for (int i = 0; i < 4; ++i) {
            int new_x = point.first + x[i];
            int new_y = point.second + y[i];
            if (new_x >= 0 && new_x <= n + 1 &&
                new_y >= 0 && new_y <= n + 1 &&
                arr[new_x][new_y] == 0 && vis[new_x][new_y] == 0) {
                vis[new_x][new_y] = 1;
                q.push({new_x, new_y});
            }
        }
    }

    for (int i = 1; i <= n; ++i) {
        if (i != 1)
            cout << endl;

        for (int j = 1; j <= n; ++j) {
            if (j != 1)
                cout << " ";

            if (vis[i][j] == 1)
                cout << 0;
            else if (arr[i][j] == 0)
                cout << 2;
            else
                cout << arr[i][j];
        }
    }

    return 0;
}