#ABC088D. 涂黑得分

涂黑得分

题目描述

\hspace{15pt}给定一个 n×mn\times m 的黑白网格,字符 ‘.’\texttt{`.'} 表示白格,字符 \texttt{`#'} 表示黑格。左上角与右下角保证都是白格。

\hspace{15pt}游戏开始前,可以把任意多个白格改成黑格,但不能改变起点 (1,1)(1,1) 和终点 (n,m)(n,m)。所有改色必须在移动开始前完成。

\hspace{15pt}随后从起点出发,每步只能上下左右移动到白格。若最终能够到达终点,得分为此前改成黑色的格子数。请计算最高得分;若原来就无法到达终点,输出 −1-1。

输入格式

\hspace{15pt}第一行输入两个整数 n,m(2≦n,m≦50)n,m\left(2\leqq n,m\leqq50\right)。

\hspace{15pt}此后 nn 行,每行输入一个长度为 mm、仅含 ‘.’\texttt{`.'} 和 \texttt{`#'} 的字符串。左上角和右下角均为 ‘.’\texttt{`.'}。

输出格式

\hspace{15pt}输出一个整数,代表最高得分;无法通关时输出 −1-1。

测试样例

3 3
..#
#..
...
2

样例 1 解释

\hspace{15pt}原网格有 77 个白格。保留路径 (1,1)→(1,2)→(2,2)→(2,3)→(3,3)(1,1)\to(1,2)\to(2,2)\to(2,3)\to(3,3) 的 55 个白格,把其余 22 个白格改成黑格即可得 22 分。任何路线至少需要 55 个格子,因此无法获得更高分。

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