水质检测
题号:NC307647
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

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

输入描述:

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

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

对于 100\% 的评测用例,保证 n \leq 1000000

输出描述:

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

输入

复制
.##.....#
.#.#.#...

输出

复制
5