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

AT_abc088_d.[ABC088D] Grid Repainting

普及/提高-

通过率：0%

AC君温馨提醒

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

题目描述

有一个纵向 HH 行、横向 WW 列的网格，每个格子被涂成白色或黑色。第 ii 行第 jj 列的格子记作 (i, j)(i,\ j)。すぬけ君想用这个网格玩如下游戏：游戏开始时，游戏角色「けぬす君」在格子 (1, 1)(1,\ 1)。玩家可以反复将けぬす君向上下左右四个方向之一移动一格。如果けぬす君只经过白色格子并到达 (H, W)(H,\ W)，则游戏通关。

在游戏开始前，すぬけ君可以将一些白色格子变为黑色，但不能改变 (1, 1)(1,\ 1) 和 (H, W)(H,\ W) 的颜色，且所有颜色的更改都必须在游戏开始前完成。

当游戏通关时，すぬけ君在游戏开始前改变格子颜色的次数即为すぬけ君的得分。请你求出すぬけ君可能取得的最大得分。如果无论如何改变格子的颜色，けぬす君都无法到达 (H, W)(H,\ W)，请输出 −1-1。

每个格子的颜色信息以字符 si, js_{i,\ j} 给出。若格子 (i, j)(i,\ j) 初始为白色，则 si, js_{i,\ j} 为 .，若初始为黑色，则 si, js_{i,\ j} 为 #。

输入格式

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

HH WW
s1,1s1,2s1,3…s1,Ws_{1,1}s_{1,2}s_{1,3}\ldots s_{1,W}
s2,1s2,2s2,3…s2,Ws_{2,1}s_{2,2}s_{2,3}\ldots s_{2,W}
⋮\vdots
sH,1sH,2sH,3…sH,Ws_{H,1}s_{H,2}s_{H,3}\ldots s_{H,W}

输出格式

请输出すぬけ君可能取得的最大得分。如果无论如何改变格子的颜色，けぬす君都无法到达 (H, W)(H,\ W)，请输出 −1-1。

输入输出样例

  • 输入#1

    3 3
..#
#..
...

    输出#1

    2

  • 输入#2

    10 37
.....................................
...#...####...####..###...###...###..
..#.#..#...#.##....#...#.#...#.#...#.
..#.#..#...#.#.....#...#.#...#.#...#.
.#...#.#..##.#.....#...#.#.###.#.###.
.#####.####..#.....#...#..##....##...
.#...#.#...#.#.....#...#.#...#.#...#.
.#...#.#...#.##....#...#.#...#.#...#.
.#...#.####...####..###...###...###..
.....................................

    输出#2

    209

说明/提示

限制条件

  • HH 是 22 到 5050 之间的整数。
  • WW 是 22 到 5050 之间的整数。
  • si,js_{i,j} 是 . 或 #（1≤i≤H, 1≤j≤W1 \leq i \leq H,\ 1 \leq j \leq W）。
  • s1,1s_{1,1} 和 sH,Ws_{H,W} 均为 .。

样例解释 1

如下图所示，如果按图中方式改变格子的颜色，可以取得得分 22。

由 ChatGPT 4.1 翻译

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

首页