← 返回题目列表

AtCoder · agc043_a

A. 范围翻转查找路线

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

考虑一个网格 H 行和 W 方格列。让 (r, c) 表示位于 r从顶部算起的第行和 c左起第 列。 每个方块都漆成黑色或白色。

网格据说是 好 当且仅当满足以下条件时:

  • 来自 (1, 1),我们可以到达 (H, W) 移动一格 向右或向下 重复 ,同时始终位于白色方块上。 如果网格良好,

请注意 (1, 1) 和 (H, W) 必须是白色。

你的任务是通过重复以下操作来使网格良好。找出完成任务所需的最少操作数。可以证明,你总是可以在有限次数的操作中完成任务。

  • 选择四个整数 r_0, c_0, r_1, c_1(1 \leq r_0 \leq r_1 \leq H, 1 \leq c_0 \leq c_1 \leq W)。对于每对 r, c (r_0 \leq r \leq r_1, c_0 \leq c \leq c_1),反转颜色 (r, c) - 即从白色到黑色,反之亦然。

约束

  • 2 \leq H, W \leq 100

输入

输入由标准输入按以下格式给出:

H W
s_{11} s_{12} \cdots s_{1W}
s_{21} s_{22} \cdots s_{2W}
 \vdots
s_{H1} s_{H2} \cdots s_{HW}

这里 s_{rc} 代表颜色 (r, c) - # 代表黑色,并且 . 代表白色。

输出

打印所需的最少操作数。


示例输入 1

3 3
.##
.#.
##.

示例输出 1

1

进行操作 (r_0, c_0, r_1, c_1) = (2, 2, 2, 2) 仅更改颜色 (2, 2),我们就完成了。


示例输入 2

2 2
#.
.#

示例输出 2

2

示例输入 3

4 4
..##
#...
###.
###.

示例输出 3

0

可能不需要任何操作。


示例输入 4

5 5
.#.#.
#.#.#
.#.#.
#.#.#
.#.#.

示例输出 4

4