贪心

思路分为两个部分：

1. 保证左右连通：
   • 每次在检测器之间的空列上，必须至少添加一个检测器打通。
   • 比如当前列是一个非空列（有#），和上一个非空列之间隔了 x 列空白，那么就需要添加 x - 1 个#。
2. 保证上下连通：
   • 检测器如果交替出现在上行和下行，那么就需要通过在当前列添加一个#实现上下连通。
   • 比如上一列只有上面有#，当前列只有下面有#，那么就需要在当前列补一个#实现上下连通（反之亦然）。

整体流程：

1. 遍历每一列：
   • 如果当前列是空的（上下都是.） –> 跳过。
   • 如果不是空的：
     • 如果之前遇到过#，并且中间隔了一段空列 –> 补中间列实现左右连通。
     • 判断当前列的#是在哪一行，和上一个不同 –> 补一个#实现上下连通。
     • 更新当前位置为新的基准。

代码实现：

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

string a, b;
// x：记录上一次非空列的位置
// z：记录当前列中检测器的分布状态（1：上行，2：下行，3：上下都有）
int x = -1, z, ans;

int main() {

    cin >> a >> b;

    for (int i = 0; i < a.size(); i ++) {

        if (a[i] == '.' && b[i] == '.') continue;
        if (x != -1)    ans += i - x - 1;       // 左右连通

        if (a[i] == '#' && b[i] == '.') {
            if (z == 2) {
                ans ++;     // 上下连通
                z = 3;
            } else {
                z = 1;
            }
        } else if (a[i] == '.' && b[i] == '#') {
            if (z == 1) {
                ans ++;     // 上下连通
                z = 3;
            } else {
                z = 2;
            }
        } else {
            z = 3;
        }
        x = i;      // 记录当前非空列的位置，作为下一个连接的起点
    }

    cout << ans;

    return 0;
}