#1661. 「USACO 2025.2 Bronze」Reflection

内存限制
512 MiB
时间限制
2000 ms
标准输入输出
题目类型
传统
评测方式
文本比较
上传者 admin
题目来源 usaco

显示标签

题目描述

Farmer John 有一块正方形画布,由一个 列的方阵表示( 为偶数)。他按照以下步骤来绘制画布:

首先,他将画布分成四个等大的象限,由通过画布中心的水平和垂直直线分隔。 其次,他在画布的右上象限中绘制了一幅美丽的画作。右上象限的每个方格或者被涂色(以 # 表示),或者未被涂色(以 . 表示)。 最后,由于他对自己的画作感到非常自豪,他将其沿此前提到的水平和垂直直线翻转到画布的其他象限中。 例如,假设 ,且 FJ 在步骤 2 中于右上象限绘制了以下画作:

.#..
.#..
.##.
....

在步骤 3 中沿水平和垂直直线翻转过后,画布将如下所示:

..#..#..
..#..#..
.##..##.
........
........
.##..##.
..#..#..
..#..#..

然而,当 FJ 熟睡时,Bessie 闯入了他的牛棚,偷走了他珍贵的画布。她彻底破坏了画布——移除了某些涂色的单元格,同时添加了某些涂色的单元格!在 FJ 醒来之前,她将画布归还给了 FJ。

FJ 想要修改他的画布,使其再次满足翻转条件:即,它是将右上象限翻转到其他各象限的结果。由于他只有有限的资源,他希望以尽可能少的操作来实现这一点,其中单次操作包括为一个方格涂色或移除一个方格的涂色。

给定 Bessie 破坏后的画布,以及一系列 )次对画布的更新,每次更新切换单个方格的状态,若它是 '#' 则切换为 '.',反之亦然。在所有更新之前,以及在每次更新之后,输出 FJ 为满足翻转条件所需要执行的最小操作数量

输入格式

输入的第一行包含整数

以下 行,每行包含 个字符,表示 Bessie 破坏后的画布。每个字符均为 #.

以下 行,每行包含整数 ,其中 ,表示一次对画布从上到下第 行,从左到右第 列的方格的更新。

输出格式

输出 行,为在所有更新之前以及在每次更新之后的

样例

输入 #1

4 5
..#.
##.#
####
..##
1 3
2 3
4 3
4 4
4 4

输出 #1

4
3
2
1
0
1

数据范围与提示

样例 1 解释:

以下画布满足翻转条件,并且可由原画布经过 4 次操作得到:

....
####
####
....

使用少于 4 次操作使原画布满足翻转条件是不可能的。

在更新 之后,画布看起来是这样的:

....
##.#
####
..##

现在需要 3 次操作使画布满足翻转条件。

在更新 之后,画布看起来是这样的:

....
####
####
..##

现在需要 2 次操作使画布满足翻转条件。

  • 测试点
  • 测试点
  • 测试点 :没有额外限制。