#ABC088D. 涂黑得分
涂黑得分
题目描述
给定一个 的黑白网格,字符 表示白格,字符 \texttt{`#'} 表示黑格。左上角与右下角保证都是白格。
游戏开始前,可以把任意多个白格改成黑格,但不能改变起点 和终点 。所有改色必须在移动开始前完成。
随后从起点出发,每步只能上下左右移动到白格。若最终能够到达终点,得分为此前改成黑色的格子数。请计算最高得分;若原来就无法到达终点,输出 。
输入格式
第一行输入两个整数 。
此后 行,每行输入一个长度为 、仅含 和 \texttt{`#'} 的字符串。左上角和右下角均为 。
输出格式
输出一个整数,代表最高得分;无法通关时输出 。
测试样例
3 3
..#
#..
...
2
样例 1 解释
原网格有 个白格。保留路径 的 个白格,把其余 个白格改成黑格即可得 分。任何路线至少需要 个格子,因此无法获得更高分。
10 37
.....................................
...#...####...####..###...###...###..
..#.#..#...#.##....#...#.#...#.#...#.
..#.#..#...#.#.....#...#.#...#.#...#.
.#...#.#..##.#.....#...#.#.###.#.###.
.#####.####..#.....#...#..##....##...
.#...#.#...#.#.....#...#.#...#.#...#.
.#...#.#...#.##....#...#.#...#.#...#.
.#...#.####...####..###...###...###..
.....................................
209