A5406. Grid Repainting
编程题
普及/提高-
知识点
题目描述
有一个纵向 $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}$ 为
在游戏开始前，すぬけ君可以将一些白色格子变为黑色，但不能改变 $(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$
> $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
输入 #2
10 37 ..................................... ...#...####...####..###...###...###.. ..#.#..#...#.##....#...#.#...#.#...#. ..#.#..#...#.#.....#...#.#...#.#...#. .#...#.#..##.#.....#...#.#.###.#.###. .#####.####..#.....#...#..##....##... .#...#.#...#.#.....#...#.#...#.#...#. .#...#.#...#.##....#...#.#...#.#...#. .#...#.####...####..###...###...###.. .....................................
输出 #2
209
说明/提示
### 限制条件
- $H$ 是 $2$ 到 $50$ 之间的整数。
- $W$ 是 $2$ 到 $50$ 之间的整数。
- $s_{i,j}$ 是
- $s_{1,1}$ 和 $s_{H,W}$ 均为
### 样例解释 1
如下图所示，如果按图中方式改变格子的颜色，可以取得得分 $2$。
- $H$ 是 $2$ 到 $50$ 之间的整数。
- $W$ 是 $2$ 到 $50$ 之间的整数。
- $s_{i,j}$ 是
. 或 #（$1 \leq i \leq H,\ 1 \leq j \leq W$）。- $s_{1,1}$ 和 $s_{H,W}$ 均为
.。### 样例解释 1
如下图所示，如果按图中方式改变格子的颜色，可以取得得分 $2$。