P1162-填涂颜色 - 从萌新到萌新的成长历程

题目传送门

题目思路

用bfs搜

思路是把0全换成2，然后从边缘开始bfs，搜到的全部换0，逆向思路

坑：首先是可能没有0，就是1就是边框。。这个要特判

再一个坑就是，需要替换成0的可能有好几个联通分支，因此要把边界检查完，而不是只检查第一个

AC代码

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

void bfs(vector<vector<int>> &a, int x, int y, int n)
{
    queue<pair<int, int>> q;
    vector<vector<int>> vis(n, vector<int>(n, 0));
    q.push({x, y});
    while (!q.empty())
    {
        pair<int, int> t = q.front();
        int i = t.first, j = t.second;
        vis[i][j] = 1;
        q.pop();
        if (i < 0 || i >= n || j < 0 || j >= n || a[i][j] == 1)
            continue;
        a[i][j] = 0;
        if (vis[i - 1 >= 0 ? i - 1 : 0][j] == 0)
            q.push({i - 1, j});
        if (vis[i + 1 < n ? i + 1 : n - 1][j] == 0)
            q.push({i + 1, j});
        if (vis[i][j - 1 >= 0 ? j - 1 : 0] == 0)
            q.push({i, j - 1});
        if (vis[i][j + 1 < n ? j + 1 : n - 1] == 0)
            q.push({i, j + 1});
    }
}

int main()
{
    int n;
    cin >> n;
    vector<vector<int>> a(n, vector<int>(n, 0));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
        {
            int x;
            cin >> x;
            a[i][j] = (x == 1 ? 1 : 2);
        }
    int x = -1;
    int y = -1;
    for (int i = 0; i < n; i++)
        if (a[0][i] == 2)
        {
            x = 0;
            y = i;
            bfs(a, x, y, n);
        }
        else if (a[n - 1][i] == 2)
        {
            x = n - 1;
            y = i;
            bfs(a, x, y, n);
        }
        else if (a[i][0] == 2)
        {
            x = i;
            y = 0;
            bfs(a, x, y, n);
        }
        else if (a[i][n - 1] == 2)
        {
            x = i;
            y = n - 1;
            bfs(a, x, y, n);
        }
    // cout << "-----------" << endl;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cout << a[i][j] << " ";
        }
        cout << endl;
    }

    return 0;
}