前言

主要为了帮助自己复习以及理解，避免学完就丢。帮助自己整理思路以及复盘，积累一些做题方法。

思考过程

• 问题提炼：
  对图里的每一个*，假设它变成了.，求与当前位置所在连通块的.的数量。
• 思路:
  1. 对图中所有非*的位置求.的连同量的集合。
     可以用并查集, dfs, bfs等进行求解.
  2. 对图中所有的*, 将其看成., 求其所在连通块的.的数量.
     遍历当前位置上, 下, 左, 右的四个方向, 合并其中根节点不同的集合, 输出该连通块的.的数量.
• 考查的知识点：
  并查集、dfs、bfs

解题方法

1. 并查集—O(n*m)代码来自

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 1010, M = N * N;
int p[M], s[M]; // 将二维映射成一维, 所以需要N*N的大小, p:每个节点的父亲节点, s:每个父节点的连通块大小
char g[N][N];   // 存储图
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};   // 上下左右四个方向向量
int n, m;       // n:行大小, m:列大小

int get(int x, int y)   // 映射方法, 将二维的坐标映射成一维的下标
{
    return x * m + y;
}
int find(int x)  // 并查集的find函数
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}
int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i++) scanf("%s", g[i]);   // 读入图
    for(int i = 0; i < n * m; i++) p[i] = i, s[i] = 1;  //初始化s和p

    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            if(g[i][j] == '.')  //对图中的每一个.
                for(int k = 0; k < 4; k++)  //遍历其四个方向上的元素
                {
                    int x = i + dx[k], y = j + dy[k];   //获取相邻元素的坐标
                    if(x >= 0 && x < n && y >= 0 && y < m && g[x][y] == '.')//对是.的元素, 添加到同一个连通块中
                    {
                        int a = get(i, j), b = get(x, y);   //映射坐标
                        a = find(a), b = find(b);   //查询父节点
                        if(a != b)  //父节点不相等, 说明当前.和该相邻的.所在的集合连通
                        {
                            s[b] += s[a];   //维护父节点所在连通块的大小
                            p[a] = b;       //更新父节点
                        }
                    }
                }
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < m; j++)
            if(g[i][j] == '.') printf(".");
            else
            {
                int fathers[4], cnt = 0;
                for(int k = 0; k < 4; k++)
                {
                    int x = i + dx[k], y = j + dy[k];
                    if(x >= 0 && x < n && y >= 0 && y < m && g[x][y] == '.')
                    {
                        int a = get(x, y);
                        fathers[cnt++] = find(a);
                    }
                }
                int sum = 1;
                if(cnt)
                {
                    sort(fathers, fathers + cnt);
                    cnt = unique(fathers, fathers + cnt) - fathers;
                    for(int k = 0; k < cnt; k++)
                        sum += s[fathers[k]];
                }
                printf("%d", sum % 10);
            }
        puts("");
    }
    return 0;
}

2. BFS—O(n*m)
主要用于填写每个点属于哪个集合, 以及统计每个集合有多少个.

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;

const int N = 1010;
typedef pair<int, int> PII;
int dx[4] = { -1, 0, 1, 0 }, dy[4] = { 0, 1, 0, -1 };
int st[N][N], mp[N][N], nums[N * N]; //st:标记数组，mp：标记每个.属于哪个集合，nums存储每个集合的.的数量
char g[N][N];   //图
int n, m, idx;  //n:行大小, m:列大小, idx:集合号的索引

void bfs(int a, int b)
{
    queue<pair<int, int>> q;
    q.push({ a, b });
    st[a][b] = 1;
    mp[a][b] = idx;

    int cnt = 1;
    while (q.size())
    {
        auto u = q.front();
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            int x = u.first + dx[i], y = u.second + dy[i];
            if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] == '.' && !st[x][y])
            {
                st[x][y] = 1;
                mp[x][y] = idx;
                cnt++;
                q.push({ x, y });
            }
        }
    }
    nums[idx++] = cnt;
}

int main()
{
    cin >> n >> m;
    for(int i = 0; i < n; i++) scanf("%s", g[i]);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (g[i][j] == '.' && !st[i][j])  //找到没标记的.进行遍历
                bfs(i, j);
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
            if (g[i][j] == '.') printf(".");
            else
            {
                int fathers[4], cnt = 0;    //去重数组fathers
                for (int k = 0; k < 4; k++)
                {
                    int x = i + dx[k], y = j + dy[k];
                    if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] == '.')
                        fathers[cnt++] = mp[x][y];
                }

                int ans = 1;
                sort(fathers, fathers + cnt);
                cnt = unique(fathers, fathers + cnt) - fathers;
                for (int k = 0; k < cnt; k++)
                    ans += nums[fathers[k]];
                printf("%d", ans % 10);
            }
        puts("");
    }
    return 0;
}

3. DFS—O(n*m)

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <queue>
using namespace std;
const int N = 1010;
typedef pair<int, int> PII;
int dx[4] = { -1, 0, 1, 0 }, dy[4] = { 0, 1, 0, -1 };

int st[N][N], mp[N][N], nums[N * N];
char g[N][N];
int n, m, idx;

int dfs(int a, int b)   //返回当前集合有多少的.
{
    st[a][b] = 1;
    mp[a][b] = idx;

    int cnt = 1;
    for(int i = 0; i < 4; i++)
    {
        int x = a + dx[i], y = b + dy[i];
        if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] == '.' && !st[x][y])
        {
            st[x][y] = 1;
            mp[x][y] = idx;
            cnt += dfs(x, y);
        }
    }
    return cnt;
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++) scanf("%s", g[i]);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (g[i][j] == '.' && !st[i][j])
            {
                //bfs(i, j);
                int cnt = dfs(i, j);
                nums[idx++] = cnt;
            }
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
            if (g[i][j] == '.') printf(".");
            else
            {
                int fathers[4], cnt = 0;
                for (int k = 0; k < 4; k++)
                {
                    int x = i + dx[k], y = j + dy[k];
                    if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] == '.')
                        fathers[cnt++] = mp[x][y];
                }
                int ans = 1;
                sort(fathers, fathers + cnt);
                cnt = unique(fathers, fathers + cnt) - fathers;
                for (int k = 0; k < cnt; k++)
                    ans += nums[fathers[k]];
                printf("%d", ans % 10);
            }
        puts("");
    }
    return 0;
}