← 返回题目列表

AtCoder · joi2022_yo2_b

B. 地毯

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

配点: 100 点

問題文

热爱时尚的Bitaro买了一张新地毯。地毯是垂直的 H 行,横 W 它具有矩形形状,分为多个列网格,每个网格的颜色为白色或黑色。从地毯上方 i 线,从左起 j 列目 (1 \leqq i \leqq H,1 \leqq j \leqq W) 中方块的颜色是字符串 S_{i} 的 j 第一个字母是 白色时 . ,# 是黑色的。

Bitaro想出了一个游戏,他将一个棋子放在地毯的左上角,通过执行几次以下操作,棋子到达地毯的右下角。

  • 与放置棋子的方块颜色不同且垂直和水平相邻的方块是 1 选择一个并将棋子移至该方格。

Bitaro 希望最大限度地减少到达目的地所需的操作次数。然而,根据地毯的图案,这可能是不可能的。

给定地毯图案的信息,编写一个程序,确定是否可以通过重复操作从左上方格到右下方格得到一块,如果可能,找到最少的操作次数。

制約

  • 1 \leqq H \leqq 500.
  • 1 \leqq W \leqq 500.
  • (H, W) \neq (1, 1).
  • S_{i} 是长度 W 是一个字符串 (1 \leqq i \leqq H).
  • S_{i} 中的每个字符是 . 或 # (1 \leqq i \leqq H).
  • H, W 是一个整数。

小課題

  1. (4 点) H = 1.
  2. (14 点) H \leqq 5,W \leqq 5.
  3. (24 点) H \leqq 30,W \leqq 30.
  4. (58 点)没有额外的限制。

评分注意事项

所有提交的内容都将通过评审系统进行评分。

如果提交的源代码为与该子作业对应的所有评分输入数据返回正确的结果,则该源代码将被识别为对于该子作业是正确的。

每次提交的分数是所提交源代码被认为正确的子任务分数的总和。

该作业的分数是该作业所有提交的最高分数。

您可以在“提交结果”选项卡上的“我的分数状态”中查看您当前的分数。


入力

输入是按以下格式从标准输入给出的。

H W
S_{1}
S_{2}
\vdots
S_{H}

出力

如果通过重复操作能够得到从左上方格到右下方格的棋子,则设置最小操作次数,如果不可能,则设置最小操作次数。 -1 到标准输出 1 行。


入力例 1

4 5
...#.
#####
...#.
#.###

出力例 1

9

例如,可以考虑图中所示的操作。

操作の 2 例の図示

在左侧的示例中 9 操作,在右侧的示例中 可以使用 13 操作将棋子从左上角的方块移动到右下角的方块。 不可能以少于

9 的次数到达目的地,所以 输出9 。

此输入示例是一个小作业。 2, 3, 4 满足约束。


入力例 2

3 3
...
...
...

出力例 2

-1

在某些情况下,可能无法从一开始就进行操作。在这种情况下,棋子不可能到达右下方格,所以-1 。

此输入示例是一个小作业。 2, 3, 4 满足约束。


入力例 3

1 5
.#.#.

出力例 3

4

此输入示例满足所有子任务约束。


入力例 4

5 5
###.#
.#...
.#..#
.####
##..#

出力例 4

12

此输入示例是一个小作业。 2, 3, 4 满足约束。


入力例 5

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

出力例 5

12

此输入示例是一个小作业。 3, 4 满足约束。