小明需要在一条 2 × n 的河床上铺设水质检测器。在他铺设之前,河床上已经存在一些检测器。如果两个检测器上下或者左右相邻,那么这两个检测器就 是互相连通的。连通具有传递性,即如果 A 和 B 连通,B 和 C 连通,那么 A 和 C 也连通。现在他需要在河床上增加铺设一些检测器使得所有的检测器都互相连通。他想知道最少需要增加铺设多少个检测器?
输入共两行,表示一个 2 × n 的河床。
每行一个长度为 n 的字符串,仅包含 ‘#’ 和 ‘.’,其中 ‘#’ 表示已经存在的 检测器,‘.’ 表示空白。
输出共 1 行,一个整数表示答案。
.##.....# .#.#.#...
5
【样例说明】
其中一种方案:
.###. . . . #
.#.######
增加了 5 个检测器
【评测用例规模与约定】
对于 100% 的评测用例,保证 n ≤ 1000000。