题目描述

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

输入格式

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

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

输出格式

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

输入输出样例

输入

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

输出

5

说明/提示

样例说明

其中一种方案：

.###. . . . #

.#.######

增加了 5 个检测器。

评测用例规模与约定

对于 100% 的评测用例，保证 n≤1000000。

思路分析：

贪心

        我们从左往右一列一列地观察数据。先删去所有空列，发现某列是否需要补检测器只和上一列有关。只有当上一列和本列都只有一个，且两列错开时才要补充。若上一列有 2 个则本列一定不要补充。

##..#
#.##.

那么如果需要补充，肯定是补充在本列，使本列变成有 2 个的情况，显然比补充在前一列更优。

根据这个贪心思想，我们可以补充完这张图使其连通：

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

再考虑之前删掉的空列：

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

不难发现，除了开头和结尾的空列，中间空了几列就要补充几个检测器，至此解决问题。

        那么我们可以将两步合在一起做：记录下上一次非空列的状态，比如 0 表示 ##，1 表示 #.，2 表示 .#。从左往右扫描，统计两列间空了多少列，直接计入答案需要补充。

对于两个非空列，只有当他们错开了，本列需要补充一个，变成 ##。

这样从左往右贪心一遍，即为答案。

实现代码：

#include <bits/stdc++.h>
using namespace std;
string str[3];
int main()
{
    cin >> str[0] >> str[1];
    int n = str[0].size(), p = 0;
    // 找到第一个非空列
    while (p < n && str[0][p] == '.' && str[1][p] == '.')
    {
        p++;
    }
    // 0: ##  1: #.  2: .#
    int last = (str[0][p] == '.') ? 2 : ((str[1][p] == '.') ? 1 : 0);
    int res = 0;
    for (p++; p < n; p++)
    {
        int cnt = 0; // 统计空列个数
        // 找到下一个非空列
        while (p < n && str[0][p] == '.' && str[1][p] == '.')
        {
            p++;
            cnt++;
        }
        if (p == n)
            break;
        res += cnt;
        int cur = (str[0][p] == '.') ? 2 : ((str[1][p] == '.') ? 1 : 0);
        if (cur && last && cur + last == 3)    // 两个非空列错开了
        {
            res++;
            last = 0;        // 补充成 ##
        }
        else
        {
            last = cur;
        }
    }
    printf("%d", res);
    return 0;
}