#CF2272B. Frogs Jump
Frogs Jump
题目描述
给定一个 的网格,网格中的每个单元格要么为空,要么包含一只青蛙。保证输入网格的每一列至少有一只青蛙。你可以选择 只青蛙并将它们从网格中移除。此后,所有剩余的青蛙将进行跳跃。
每只青蛙可以向上、下、左或右跳跃 个单元格,但不能跳出网格。所有青蛙必须选择一个合法的方向并同时恰好跳跃一次。跳跃后,网格中每一行和每一列的青蛙数量必须保持不变。
注意:
- 即使两只青蛙的跳跃方向冲突,它们仍然可以跳到各自的目标单元格。
- 允许多只青蛙跳到同一个单元格,因为一个单元格可以容纳任意多只青蛙。
求最小的 ,使得存在一种合法的跳跃方案。
输入格式
每个测试包含多个测试用例。第一行包含测试用例的数量 ()。接下来是每个测试用例的描述。
对于每个测试用例,第一行包含一个整数 (),其中 是网格的列数。
接下来两行各包含一个长度为 的字符串;用字符 表示包含青蛙的单元格,用字符 表示空的单元格。
保证输入网格的每一列至少有一只青蛙。
保证所有测试用例的 之和不超过 。
输出格式
对于每个测试用例,输出一行,包含最小的 ,使得存在一种合法的跳跃方案。
样例
4
2
ff
oo
2
fo
of
3
fof
ofo
1
f
o
0
0
1
1
说明
在第一个测试用例中,两只青蛙可以跳到对方的单元格。
在第二个测试用例中,左边的青蛙可以向下跳,右边的青蛙可以向上跳。跳跃后,每行和每列的青蛙总数保持为 。
| o | f |
| f | o |
在第三个测试用例中,三只青蛙可以全部跳到同一个单元格 ,但这不是合法的答案,因为第一列的青蛙数量从 变为了 。
| o | f f f | o |
| o | o | o |
来源
导入自 Codeforces — Codeforces Round 1130 (Div. 2)。