Farmer John 有一块正方形画布,由一个 行 列的方阵表示(, 为偶数)。他按照以下步骤来绘制画布:
首先,他将画布分成四个等大的象限,由通过画布中心的水平和垂直直线分隔。
其次,他在画布的右上象限中绘制了一幅美丽的画作。右上象限的每个方格或者被涂色(以 #
表示),或者未被涂色(以 .
表示)。
最后,由于他对自己的画作感到非常自豪,他将其沿此前提到的水平和垂直直线翻转到画布的其他象限中。
例如,假设 ,且 FJ 在步骤 2 中于右上象限绘制了以下画作:
在步骤 3 中沿水平和垂直直线翻转过后,画布将如下所示:
..#..#..
..#..#..
.##..##.
........
........
.##..##.
..#..#..
..#..#..
然而,当 FJ 熟睡时,Bessie 闯入了他的牛棚,偷走了他珍贵的画布。她彻底破坏了画布——移除了某些涂色的单元格,同时添加了某些涂色的单元格!在 FJ 醒来之前,她将画布归还给了 FJ。
FJ 想要修改他的画布,使其再次满足翻转条件:即,它是将右上象限翻转到其他各象限的结果。由于他只有有限的资源,他希望以尽可能少的操作来实现这一点,其中单次操作包括为一个方格涂色或移除一个方格的涂色。
给定 Bessie 破坏后的画布,以及一系列 ()次对画布的更新,每次更新切换单个方格的状态,若它是 '#' 则切换为 '.',反之亦然。在所有更新之前,以及在每次更新之后,输出 FJ 为满足翻转条件所需要执行的最小操作数量 。