#CF2272B. Frogs Jump

Frogs Jump

题目描述

给定一个 2×n2 \times n 的网格,网格中的每个单元格要么为空,要么包含一只青蛙。保证输入网格的每一列至少有一只青蛙。你可以选择 kk 只青蛙并将它们从网格中移除。此后,所有剩余的青蛙将进行跳跃。

每只青蛙可以向上、下、左或右跳跃 11 个单元格,但不能跳出网格。所有青蛙必须选择一个合法的方向并同时恰好跳跃一次。跳跃后,网格中每一行和每一列的青蛙数量必须保持不变。

注意:

  • 即使两只青蛙的跳跃方向冲突,它们仍然可以跳到各自的目标单元格。
  • 允许多只青蛙跳到同一个单元格,因为一个单元格可以容纳任意多只青蛙。

求最小的 kk,使得存在一种合法的跳跃方案。

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 tt(1≤t≤1041 \le t \le 10^4)。接下来是每个测试用例的描述。

对于每个测试用例,第一行包含一个整数 nn(1≤n≤2⋅1051 \le n \le 2 \cdot 10^5),其中 nn 是网格的列数。

接下来两行各包含一个长度为 nn 的字符串;用字符 f\texttt{f} 表示包含青蛙的单元格,用字符 o\texttt{o} 表示空的单元格。

保证输入网格的每一列至少有一只青蛙。

保证所有测试用例的 nn 之和不超过 2⋅1052 \cdot 10^5。

输出格式

对于每个测试用例,输出一行,包含最小的 kk,使得存在一种合法的跳跃方案。

样例

4
2
ff
oo
2
fo
of
3
fof
ofo
1
f
o
0
0
1
1

说明

在第一个测试用例中,两只青蛙可以跳到对方的单元格。

在第二个测试用例中,左边的青蛙可以向下跳,右边的青蛙可以向上跳。跳跃后,每行和每列的青蛙总数保持为 11。

of
fo

在第三个测试用例中,三只青蛙可以全部跳到同一个单元格 (1,2)(1,2),但这不是合法的答案,因为第一列的青蛙数量从 11 变为了 00。

of f fo
ooo

来源

导入自 Codeforces — Codeforces Round 1130 (Div. 2)。