分数: 400 点
问题陈述
我们有一个 H \times W 网格,其方块被涂成黑色或白色。广场位于 i从顶部开始的第行和 j从左边算起的第列表示为 (i, j).
Snuke 想在此网格上玩以下游戏。游戏一开始,广场上有一个叫Kenus的角色 (1, 1)。玩家反复将 Kenus 向上、向下、向左或向右移动一格。当 Kenus 到达方块时游戏结束 (H, W) 仅通过白色方块。
Snuke开始游戏之前,他可以将一些白色方块的颜色更改为黑色。但是,他不能改变正方形的颜色 (1, 1) 和 (H, W)。另外,颜色的变化必须全部在比赛开始前进行。
当游戏结束时,Snuke的得分将是他在游戏开始前改变方块颜色的次数。找到 Snuke 可以达到的最大可能分数,或打印 -1 如果游戏无法完成,即Kenus永远无法到达方块 (H, W) 无论 Snuke 如何改变方块的颜色。
方块的颜色作为字符提供给您 s_{i, j}。如果是正方形 (i, j) 最初涂成白色, s_{i, j} is .;如果是正方形 (i, j) 最初涂成黑色, s_{i, j} is #.
约束
- H 是介于 2 和 50 (含)。
- W 是介于 2 和 50 (含)。
- s_{i, j} is
.or#(1 \leq i \leq H, 1 \leq j \leq W). - s_{1, 1} 和 s_{H, W} 是
..
输入
输入由标准输入按以下格式给出:
H W
s_{1, 1}s_{1, 2}s_{1, 3} ... s_{1, W}
s_{2, 1}s_{2, 2}s_{2, 3} ... s_{2, W}
: :
s_{H, 1}s_{H, 2}s_{H, 3} ... s_{H, W}
输出
打印 Snuke 可以达到的最大可能分数,或打印 -1 如果游戏无法完成。
示例输入 1
3 3 ..# #.. ...
示例输出 1
2
分数 2 可以通过改变方块的颜色来实现,如下所示:

示例输入 2
10 37 ..................................... ...#...####...####..###...###...###.. ..#.#..#...#.##....#...#.#...#.#...#. ..#.#..#...#.#.....#...#.#...#.#...#. .#...#.#..##.#.....#...#.#.###.#.###. .#####.####..#.....#...#..##....##... .#...#.#...#.#.....#...#.#...#.#...#. .#...#.#...#.##....#...#.#...#.#...#. .#...#.####...####..###...###...###.. .....................................
示例输出 2
209