题目描述

我们有一个 $H \\times W$ 的网格，格子被涂成黑色或白色。第 $i$ 行从上到下，第 $j$ 列从左到右标记为 $(i, j)$。
Snuke 想在这个网格上玩以下游戏。游戏开始时，在方格 $(1, 1)$ 上有一个叫 Kenus 的角色。玩家可以重复将 Kenus 向上、向下、向左或向右移动一个方格。当 Kenus 经过的方格只有白色方格时，游戏结束。
在 Snuke 开始游戏之前，他可以将一些白色方格的颜色改变为黑色。然而，他不能改变方格 $(1, 1)$ 和 $(H, W)$ 的颜色。并且，颜色的改变必须在游戏开始之前全部完成。
游戏结束后，Snuke 的得分将是游戏开始之前更改方格颜色的次数。找到 Snuke 可以达到的最大可能得分，或者如果游戏无法完成，则输出 -1，即无论 Snuke 如何改变方格的颜色，Kenus 都无法到达方格 $(H, W)$。

方格的颜色用字符 $s_{i, j}$ 表示。如果方格 $(i, j)$ 最初被涂成白色，则 $s_{i, j}$ 为 .；如果方格 $(i, j)$ 最初被涂成黑色，则 $s_{i, j}$ 为 #。

约束条件

• $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}$ 是 .。

输入

从标准输入中以以下格式给出输入：

$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