D - Grid Repainting（网格重新上色）

时间限制：2 秒 内存限制：256 MB 分值：400 分

---

题目描述

给定一个大小为 H × W 的网格，每个格子要么是黑色，要么是白色。 从上到下第 i 行、从左到右第 j 列的格子用 (i, j) 表示。

Snuke 想在这个网格上玩一个游戏。游戏规则如下：

• 游戏开始时，角色 Kenus 位于格子 ​**(1,1)**​。
• 玩家可以不断操作 Kenus，​上下左右移动 1 格​。
• 游戏的目标是： 让 Kenus 仅经过白色格子，到达格子 (H, W)。

在游戏开始前，Snuke 可以将一些白色格子涂成黑色，用来增加游戏难度。

但是——

• (1,1) 和 (H,W) 这两个格子不能被涂黑。
• 所有颜色修改必须在游戏开始前一次性完成。

当游戏完成后，Snuke 会获得一个得分： 得分 = 他在游戏开始前涂黑的格子数目。

你的任务是：

求 Snuke 能获得的最大得分。

如果无论怎样涂黑（保持 (1,1) 和 (H,W) 为白色）， Kenus 仍然 ​**无法从 (1,1) 走到 (H,W)**​， 则输出 -1。

---

输入格式

从标准输入读取以下内容：

H W
s1
s2
...
sH

• 每个 s[i][j] 为：
  • '.' ：白色
  • '#' ：黑色
• 且保证 s[1][1] = '.'，s[H][W] = '.'

---

输出格式

输出一个整数：

• 能达到的 ​最大得分​（可涂黑的白格数量）
• 若游戏无法完成（无法到达 (H,W)），输出 -1

---

数据范围

• 2 ≤ H ≤ 50
• 2 ≤ W ≤ 50
• s[i][j] ∈ {'.', '#'}

---

样例 1

输入

3 3
..#
#..
...

输出

2

说明

可以通过恰当地将部分白格涂黑，使最终仍存在一条从 (1,1) 到 (3,3) 的全白路径，且涂黑格子数最大为 2。

（你可以在课件中展示：只保留一条窄路径，其余尽可能染黑。）

---

样例 2

输入

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

输出

209

---