← 返回题目列表

AtCoder · awc0012_d

D. 逃离迷宫

中文机器翻译题面 查看原题

分数: 400 分

问题陈述

高桥被困在一栋老建筑内的迷宫中。

建筑物表示为一个网格,其中 N 行和 M 列。牢房位于 i从顶部开始的第行和 j从左边算起的第列称为单元格 (i, j)。的状态 i- 网格的第行由字符串表示 S_i:如果 j- 第一个字符 S_i is #,然后是单元格 (i, j) 是一堵墙;如果是的话 .,然后是单元格 (i, j) 是一段。

高桥目前在牢房 (1, 1) 并旨在到达牢房的出口 (N, M) 在右下角。

在一次操作中,高桥可以从当前单元格移动到四个相邻单元格之一(上、下、左或右)。然而,他无法移出网格。如果目标单元格是一个通道,他只需移动到那里即可。如果目标单元格是一堵墙,他会用锤子摧毁墙,将其变成一条通道,然后移动到那里。每破坏一堵墙,破坏数量就会增加 1。被破坏并转化为通道的细胞此后仍然是通道。锤子的使用次数没有限制,移动次数也没有限制。

由于高桥可以根据需要多次破坏墙壁,因此他总是可以到达牢房 (N, M)。求高桥离开牢房需要摧毁的最少墙壁数量 (1, 1) 到单元格 (N, M).

保证电池 (1, 1) 和细胞 (N, M) 始终是段落。

约束

  • 1 \leq N \leq 500
  • 1 \leq M \leq 500
  • N, M 是整数
  • S_i (1 \leq i \leq N) 是一个长度为的字符串 M 组成 # 和 .
  • 的 树的 1st 字符 S_1 is .
  • 的 树的 M- 第一个字符 S_N is .

输入

N M
S_1
S_2
\vdots
S_N
  • 第一行包含行数 N 和列数 网格的 M ,以空格分隔。
  • 的 树的 (1 + i)第行 (1 \leq i \leq N) 包含一个字符串 S_i 长度 M 代表的状态 i- 网格的第行。的 j- 第一个字符 S_i 代表cell的状态 (i, j),其中 # 指一堵墙,并且 . 表示一段。

输出

在一行中打印出高桥从牢房出发需要摧毁的最少墙壁数量 (1, 1) 到单元格 (N, M).


示例输入 1

3 5
...#.
.###.
...#.

示例输出 1

1

示例输入 2

3 3
...
...
...

示例输出 2

0

示例输入 3

5 7
..#.#.#
.#...#.
##.#.##
.#...#.
..#.#..

示例输出 3

2

示例输入 4

10 10
..........
.########.
..........
.########.
..........
.########.
..........
.########.
..........
..........

示例输出 4

0

示例输入 5

1 1
.

示例输出 5

0

示例输入 6

3 5
...#.
.###.
...#.

示例输出 6

1

示例输入 7

3 3
...
...
...

示例输出 7

0

示例输入 8

5 7
.#.#.#.
.#.#.#.
.#.#.#.
.#.#.#.
.......

示例输出 8

0

示例输入 9

10 10
..........
.########.
..........
########.#
..........
.########.
..........
########.#
..........
..........

示例输出 9

0

示例输入 10

1 1
.

示例输出 10

0