← 返回题目

题库练习 Grid Repainting

← 上一题下一题 →

A5406 | $Grid Repainting$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

有一个纵向 $H$ 行、横向 $W$ 列的网格，每个格子被涂成白色或黑色。第 $i$ 行第 $j$ 列的格子记作 $(i,\ j)$。すぬけ君想用这个网格玩如下游戏：游戏开始时，游戏角色「けぬす君」在格子 $(1,\ 1)$。玩家可以反复将けぬす君向上下左右四个方向之一移动一格。如果けぬす君只经过白色格子并到达 $(H,\ W)$，则游戏通关。 在游戏开始前，すぬけ君可以将一些白色格子变为黑色，但不能改变 $(1,\ 1)$ 和 $(H,\ W)$ 的颜色，且所有颜色的更改都必须在游戏开始前完成。 当游戏通关时，すぬけ君在游戏开始前改变格子颜色的次数即为すぬけ君的得分。请你求出すぬけ君可能取得的最大得分。如果无论如何改变格子的颜色，けぬす君都无法到达 $(H,\ W)$，请输出 $-1$。 每个格子的颜色信息以字符 $s_{i,\ j}$ 给出。若格子 $(i,\ j)$ 初始为白色，则 $s_{i,\ j}$ 为 .，若初始为黑色，则 $s_{i,\ j}$ 为 #。

输入格式

输入按以下格式从标准输入给出。 > $H$ $W$ > $s_{1,1}s_{1,2}s_{1,3}\ldots s_{1,W}$ > $s_{2,1}s_{2,2}s_{2,3}\ldots s_{2,W}$ > $\vdots$ > $s_{H,1}s_{H,2}s_{H,3}\ldots s_{H,W}$

输出格式

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

输入输出样例

输入 #1

3 3
..#
#..
...

输出 #1

输入 #2

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

输出 #2

C++ 编辑器

输入

输出