Flood Fill算法

介绍

• 基本作用：寻找连通块
• 基本方法：BFS
• 适用题目：需要寻找若干连通块的题目

顾名思义，Flood Fill算法就是像洪水泛滥一样去寻找周围符合条件的区域，采用BFS可以完成先从自身最近的点寻找随后逐步扩展。

代码思路

1. 用函数寻找一个连通块。
2. 传入坐标形参。
3. 将形参坐标的状态改变，表示已经访问过（标记是为了避免重复遍历）。
4. 创建队列存放坐标，将形参坐标放入队列。
5. 循环（队列中有元素就一直循环）
6. 将队列队头的坐标拿出。
7. 判断当前坐标条件是否符合要求（范围、标记状态、是否属于连通块）
8. 满足则加入到队尾，并标记状态。

题目应用

1097. 池塘计数(算法提高课)

1097. 池塘计数

思路：

Flood Fill的简单应用，直接套用即可。遍历地图上的点，发现为'W'并且未访问的点即调用BFS函数。

代码：

#include <bits/stdc++.h>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 1010;

int n, m;
char g[N][N];
bool st[N][N];
int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1}, dy[] = {0, 1, 1, 1, 0, -1, -1, -1};

void bfs(int x, int y)
{
    st[x][y] = true;

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

    while(q.size())
    {
        PII tmp = q.front();
        q.pop();

        for(int i = 0; i < 8; i++)
        {
            int nx = tmp.x + dx[i], ny = tmp.y + dy[i];

            if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;

            if(st[nx][ny] || g[nx][ny] == '.') continue;

            st[nx][ny] = true;
            q.push({nx, ny});
        }
    }
}

int main()
{
    cin >> n >> m;
    for(int i = 0; i < n; i++) cin >> g[i];

    int ans = 0;
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < m; j++)
        {
            if(g[i][j] == 'W' && !st[i][j])
            {
                bfs(i, j);
                ans ++;
            }
        }
    }

    cout << ans << endl;

    return 0;
}

1098. 城堡问题(算法提高课)

1098.城堡问题

思路：

该题比较特殊，每个空间的值代表周围是否有墙，所以要用到二进制转换的技巧。
num >> x & 1,可以判断，num二进制的第x-1位是否为1。
由于还要找出最大的房间，所以BFS函数要返回一个int值。
我们可以在队列循环开始时就将空间大小加一即可。

代码：

#include <bits/stdc++.h>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 55;

int n, m;
int g[N][N];
bool st[N][N];
int dx[] = {0, -1, 0, 1}, dy[] = {-1, 0, 1, 0};

int bfs(int x, int y)
{
    int res = 0;
    st[x][y] = true;

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

    while(q.size())
    {
        PII tmp = q.front();
        q.pop();
        res ++;

        for(int i = 0; i < 4; i++)
        {
            if(g[tmp.x][tmp.y] >> i & 1) continue;
            int nx = tmp.x + dx[i], ny = tmp.y + dy[i];

            if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if(st[nx][ny]) continue;

            st[nx][ny] = true;
            q.push({nx, ny});
        }
    }

    return res;
}

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

    int ans = 0, num = 0;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
        {
            if(!st[i][j])
            {
                num ++;
                int t = bfs(i, j);
                ans = max(ans, t);
            }            
        }

    cout << num << endl;
    cout << ans << endl;

    return 0;
}

1106. 山峰和山谷(算法提高课)

1106.山峰和山谷

思路：

该题不仅要找到连通块（高度相同的坐标），还要判断连通块与周围非连通块的大小关系。
在探索周围坐标时特判一下即可，判断与x，y不相同高度的坐标。

代码：

#include <bits/stdc++.h>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 1010;

int n;
int g[N][N];
bool st[N][N];
int dx[] = {-1, -1, -1, 0, 1, 1, 1, 0}, dy[] = {-1, 0, 1, 1, 1, 0, -1, -1};
int peak, valley;

int bfs(int x, int y)
{
    bool high = false;
    bool low = false;

    st[x][y] = true;

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

    while(q.size())
    {
        PII tmp = q.front();
        q.pop();

        for(int i = 0; i < 8; i++)
        {
            int nx = tmp.x + dx[i], ny = tmp.y + dy[i];
            if(nx < 0 || nx >= n || ny < 0 || ny >= n) continue;

            if(g[nx][ny] != g[tmp.x][tmp.y])
            {
                if(g[nx][ny] > g[tmp.x][tmp.y]) high = true;
                if(g[nx][ny] < g[tmp.x][tmp.y]) low = true;
            }
            else if(!st[nx][ny])
            {
                st[nx][ny] = true;
                q.push({nx, ny});
            }
        }
    }

    if(high && low) return -1;
    else if(!high && !low) return 0;
    else if(!high) return 1;
    else return 2;
}

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

    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            if(!st[i][j])
            {

                int t = bfs(i, j);
                if(t == 0) peak ++, valley ++;
                if(t == 1) peak ++;
                if(t == 2) valley ++;
            }
        }
    }

    cout << peak << " " << valley << endl;

    return 0;
}

1106. 2060. 奶牛选美(寒假每日一题2022)

AcWing 2060. 奶牛选美

思路：

该题的实质其实就是求两个连通块的点之间的最短曼哈顿距离。
由于数据量比较小（最多有2500个点）,所以我们完全可以将两个连通块的点存下来，
再暴力循环求出最短曼哈顿距离（O(n ^ 2)）。
最后，记得答案减一。

代码：

#include <bits/stdc++.h>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 55;

int n, m;
char g[N][N];
bool st[N][N];
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
vector<PII>s1, s2;

void bfs(int x, int y, int cnt)
{
    st[x][y] = true;

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


    while(q.size())
    {
        PII tmp = q.front();
        q.pop();
        if(cnt == 1) s1.push_back({tmp.x, tmp.y});
        else s2.push_back({tmp.x, tmp.y});

        for(int i = 0; i < 4; i++)
        {
            int nx = tmp.x + dx[i], ny = tmp.y + dy[i];

            if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if(g[nx][ny] == '.' || st[nx][ny]) continue;

            st[nx][ny] = true;
            q.push({nx, ny});

        }
    }
}

int main()
{
    cin >> n >> m;
    for(int i = 0; i < n; i++) cin >> g[i];

    int cnt = 1;
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < m; j++)
        {
            if(g[i][j] == 'X' && !st[i][j])
            {
                bfs(i, j, cnt);
                cnt ++;
            }
        }
    }

    int ans = INT_MAX;
    for(auto p1 : s1)
    {
        for(auto p2 : s2)
        {
            int t = abs(p1.x - p2. x) + abs(p1.y - p2.y);
            ans = min(ans, t);
        }
    }

    cout << ans - 1 << endl;

    return 0;
}