P12135 [蓝桥杯 2025 省 B] 水质检测

题目描述

小明需要在一条 $2\times n$ 的河床上铺设水质检测器。在他铺设之前，河床上已经存在一些检测器。如果两个检测器上下或者左右相邻，那么这两个检测器就是互相连通的。连通具有传递性，即如果 $A$ 和 $B$ 连通，$B$ 和 $C$ 连通，那么 $A$ 和 $C$ 也连通。现在他需要在河床上增加铺设一些检测器使得所有的检测器都互相连通。他想知道最少需要增加铺设多少个检测器？

输入格式

输入共两行，表示一个 $2\times n$ 的河床。

每行一个长度为 $n$ 的字符串，仅包含 # 和 .，其中 # 表示已经存在的检测器，. 表示空白。

输出格式

输出共 $1$ 行，一个整数表示答案。

输入输出样例 #1

输入 #1

.##.....#
.#.#.#...

输出 #1

5

说明/提示

样例说明

其中一种方案：

.###....#
.#.######

增加了 5 个检测器。

评测用例规模与约定

对于 $100\%$ 的评测用例，保证 $n\le 1000000$。

C++实现

#include <bits/stdc++.h>
using namespace std;
int main()
{
    string s1, s2;
    cin >> s1 >> s2;
    int len = s1.size();
    int num = 0; // 计数器
    int l = len, r = 0;
    for (int i = 0; i < len; i++)    {
        if (s1[i] == '#' || s2[i] == '#')        {
            l = min(l, i);
            r = max(r, i);
        }
    }
    for (int i = l; i < r; i++)    {
        if (s1[i] == '#' && s1[i + 1] == '.' && s2[i] == '.')        {
            num++;
            s1[i + 1] = '#';
        }
        if (s1[i] == '.' && s2[i + 1] == '.' && s2[i] == '#')
        {
            num++;
            s2[i + 1] = '#';
        }
        if (s1[i] == '#' && s2[i] == '#' && s2[i + 1] == '.' && s1[i + 1] == '.')        {
            int p = i, q = i;
            for (int j = i + 1; j <= r; j++)            {
                if (s1[j] == '#')                {
                    p = j;
                    break;
                }
                if (s2[j] == '#')                {
                    q = j;
                    break;
                }
            }
            if (p >= q)            {
                s1[i + 1] = '#';
                num++;
            }
            else
            {
                s2[i + 1] = '#';
                num++;
            }
        }
    }
    cout << num;
    return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容