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

AT_abc213_e.[ABC213E] Stronger Takahashi

提高+/省选-

通过率：0%

AC君温馨提醒

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

题目描述

有一座城市被划分为 HH 行 WW 列的格子状区块。从上往下第 ii 行，从左往右第 jj 列的区块，若 Si,jS_{i,j} 为 .，则表示道路；若为 #，则表示围墙。

高桥君打算从自己家出发去鱼店买东西。高桥君的家在城市的左上角区块，鱼店在城市的右下角区块。

高桥君可以从当前所在的区块移动到上下左右相邻的道路区块。不能走出城市外部，也不能移动到围墙区块。不过，高桥君力大无穷，可以每次用一拳将任意 2×22\times 2 的区块内的围墙全部打碎变成道路。

请你求出高桥君到达鱼店至少需要出拳多少次。

输入格式

输入以以下格式从标准输入给出。

HH WW
S1,1…S1,WS_{1,1} \ldots S_{1,W}
⋮\vdots
SH,1…SH,WS_{H,1} \ldots S_{H,W}

输出格式

请输出答案。

输入输出样例

  • 输入#1

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

    输出#1

    1

  • 输入#2

    5 7
.......
######.
.......
.######
.......

    输出#2

    0

  • 输入#3

    8 8
.#######
########
########
########
########
########
########
#######.

    输出#3

    5

说明/提示

限制条件

  • 2≤H,W≤5002 \leq H, W \leq 500
  • H,WH, W 为整数
  • Si,jS_{i,j} 仅为 . 或 #
  • S1,1S_{1,1} 和 SH,WS_{H,W} 均为 .

样例解释 1

例如，如果破坏用 * 表示的 2×22\times 2 区块内的围墙，就能到达鱼店。

..#..
#.**#
##**#
#.#.#
..#..

被破坏的 2×22\times 2 区块不要求全部为围墙。

样例解释 2

虽然需要绕远路，但无需破坏任何围墙也能到达鱼店。

由 ChatGPT 4.1 翻译

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

首页