题目详情题解（0）讨论（0）提交记录（0）

AT_agc043_a.[AGC043A] Range Flip Find Route

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

我们有一个 HH 行 WW 列的网格。我们用 (r,c)(r, c) 表示从上到下第 rr 行、从左到右第 cc 列的格子。每个格子要么是白色，要么是黑色。

当且仅当存在如下路径时，我们称这个网格为“良好”状态：

  • 总是只经过白色格子，从 (1,1)(1, 1) 出发，每次只能向右或向下移动一格，最终到达 (H,W)(H, W)。

请注意，如果网格处于“良好”状态，则 (1,1)(1, 1) 和 (H,W)(H, W) 必须都是白色。

你的任务是通过以下操作，将网格变为“良好”状态。请计算最少需要操作多少次。可以证明，经过有限次操作后一定可以达到“良好”状态。

  • 选择四个整数 r0,c0,r1,c1r_0, c_0, r_1, c_1（1≤r0≤r1≤H, 1≤c0≤c1≤W1 \leq r_0 \leq r_1 \leq H,\ 1 \leq c_0 \leq c_1 \leq W）。对于所有满足 r0≤r≤r1, c0≤c≤c1r_0 \leq r \leq r_1,\ c_0 \leq c \leq c_1 的格子 (r,c)(r, c)，将其颜色反转（白变黑，黑变白）。

输入格式

输入通过标准输入给出，格式如下：

HH WW
s11 s12 ⋯ s1Ws_{11}\ s_{12}\ \cdots\ s_{1W}
s21 s22 ⋯ s2Ws_{21}\ s_{22}\ \cdots\ s_{2W}
⋮\vdots
sH1 sH2 ⋯ sHWs_{H1}\ s_{H2}\ \cdots\ s_{HW}

其中，srcs_{rc} 为 # 或 .，# 表示 (r,c)(r, c) 是黑色，. 表示 (r,c)(r, c) 是白色。

输出格式

输出最少的操作次数。

输入输出样例

  • 输入#1

    3 3
.##
.#.
##.

    输出#1

    1

  • 输入#2

    2 2
#.
.#

    输出#2

    2

  • 输入#3

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

    输出#3

    0

  • 输入#4

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

    输出#4

    4

说明/提示

限制

  • 2≤H,W≤1002 \leq H, W \leq 100

样例解释 1

只需对 (r0,c0,r1,c1)=(2,2,2,2)(r_0, c_0, r_1, c_1) = (2, 2, 2, 2)，即只改变格子 (2,2)(2, 2) 的颜色即可。

样例解释 3

有些情况下不需要进行任何操作。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页