P1162 填图颜色 洛谷（BFS的简单应用）

题目描述

由数字 $0$ 组成的方阵中，有一任意形状闭合圈，闭合圈由数字 $1$ 构成，围圈时只走上下左右 $4$ 个方向。现要求把闭合圈内的所有空间都填写成 $2$。例如：$6\times 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 \le n \le 30)$。

接下来 $n$ 行，由 $0$ 和 $1$ 组成的 $n \times n$ 的方阵。

方阵内只有一个闭合圈，圈内至少有一个 $0$。

//感谢黄小U饮品指出本题数据和数据格式不一样. 已修改(输入格式)

输出格式

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

样例 #1

样例输入 #1

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

样例输出 #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

提示

对于 $100\%$ 的数据，$1 \le n \le 30$。

讲解

这道题其实用BFS挺简单的，就是注意索引从1开始，相当于在输入矩阵的最外层套一层0，然后从外层搜索，就ok了。这里有个小技巧就是把外围的0变成2，然后最后直接输出2-a[i][j]就行了，这样外层的0还是0,1还是1，内层的0就是2了。

源代码

#include <bits/stdc++.h>

using namespace std;

const int N = 40;

typedef pair<int, int> PII;

int n;
int a[N][N];
int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};

void search(int x, int y)
{
    queue<PII> q;
    q.push({x, y});

    while(q.size())
    {
        auto t = q.front();
        q.pop();

        int x1 = t.first, y1 = t.second;
        // cout <<x1 <<' ' << y1 <<endl;
        a[x1][y1] = 2;
        for (int i = 0; i < 4; i ++ )
        {
            int xx = x1 + dx[i], yy = y1 + dy[i];
            if (xx >= 0 and xx <= n + 1 and yy >= 0 and yy <= n + 1 and a[xx][yy] == 0) q.push({xx, yy});
        }

    }
}

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

    search(0, 0);

    // cout <<endl;
    for (int i = 1; i <= n; i ++)
    {
        for (int j = 1; j <= n; j ++ )
        {
            cout << 2 - a[i][j] << " \n"[j == n];
        }
    }

}