← 返回题目列表

Codeforces · 329/B

B. Biridian 森林

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

你是一名麦克兽饲养员,目前正处于成为麦克兽大师的旅程中。你当前的障碍是穿过臭名昭著的比瑞迪安森林。

森林

Biridian Forest 是一个由 r 行和 c 列组成的二维网格。 Biridian Forest 中的每个单元格可能包含一棵树,也可能是空的。一个空的单元格可能被零个或多个麦克蒙饲养员占据(森林中也可能有除你之外的饲养员)。麦克兽饲养员(包括你)无法进入有树的牢房。其中一个单元被指定为出口单元。

初始网格,包括您的初始位置、出口单元以及所有其他饲养员的初始位置,都会提供给您。这是此类网格的示例(来自第一个示例):

移动

饲养员(包括你)可以在森林中移动。在一次移动中,饲养员可以执行以下操作之一:

- 不执行任何操作。
- 从当前单元格移动到四个相邻单元格之一(如果两个单元格共享一侧,则它们是相邻的)。请注意,饲养员不能进入有树木的牢房。
- 如果你位于出口牢房,你可以离开森林。只有你可以执行此动作 - 所有其他麦克蒙饲养员都不会使用此类型的动作离开森林。

每次你做出一个动作后,其他每个饲养员都会同时做出一个动作(每个饲养员选择的动作可能不同)。

麦克兽战斗

如果你和 t (t > 0) 个 mikemon 饲养员位于同一个单元格,那么届时将会发生 t 个 mikemon 战斗(因为你将与每个 t 个饲养员战斗一次)。战斗结束后,所有这些t饲养员都会离开森林去治愈各自的mikemon。

请注意,当你离开森林时,就不会再发生更多的麦克兽战斗,即使在那之后另一个麦克兽饲养员立即移动到出口牢房。另请注意,战斗仅发生在您和其他饲养员之间 - 其他两个饲养员之间不会发生战斗(单个细胞中可能有多个饲养员共存)。

你的目标

你想离开森林。为此,您必须进行一系列动作,并以最终类型的动作结束。然而,在你采取任何行动之前,你需要在你的个人虚拟偶像博客上发布这个序列。然后,你将忠实地遵循这一系列动作。

其他育种者的目标

因为您在博客中发布了该序列,所以其他饲养员甚至在您迈出第一步之前都会知道您的确切移动顺序。如果可能的话,所有它们都会以这样的方式移动,以保证与你进行一场麦克蒙战斗。那些无法与你战斗的饲养员将一事无成。

你的任务

打印您必须参加的 mikemon 战斗的最小数量,假设您选择了最小化该数量的移动顺序。请注意,您不需要尽量减少移动次数。

输入

第一行由两个整数组成:r和c(1≤r,c≤1000),表示Biridian森林的行数和列数。接下来的 r 行将分别描述地图的一行,其中每个字符代表单个单元格的内容:

- 'T':被树占据的单元格。
- 'S':一个空单元格,以及您的起始位置。地图上只会出现一次这种情况。
- 'E':一个空单元格,出口所在的位置。地图上只会出现一次这种情况。
- 数字(0-9):由数字X表示的单元格意味着该单元格是空的并且被X个饲养员占据(特别是,如果X为零,则意味着该单元格没有被任何饲养员占据)。

保证您可以通过一系列移动从起始位置到达出口单元。

输出

单行表示如果您选择最小化此数量的策略,则您必须参加的最小可能的麦克蒙战斗数量。

示例

输入 #1

5 7
000E0T3
T0TT0T0
010T0T0
2T0T0T0
0T0S000

输出 #1

3

输入 #2

1 4
SE23

输出 #2

2

注意

下图说明了第一个示例。蓝线表示您应该在博客中发布的可能的操作顺序:

地图左侧的三个饲养员将能够与你战斗 - 孤独的饲养员可以简单地留在他的位置直到你来,而另外两个饲养员可以移动到孤独的饲养员所在的地方并留在那里直到你来。右边的三个饲养员没有办法与你战斗,所以他们会留在自己的位置。

对于第二个示例,您应该在博客中发布此序列:

发生的情况如下。首先,将一个单元格向右移动。

然后,出口右侧的两个饲养员将同时向左移动。其他三个饲养员无法与你战斗,所以他们不会采取任何行动。

你最终和 2 个饲养员在同一个牢房里,所以进行了 2 场麦克兽战斗。这些战斗结束后,所有对手都离开了森林。

最后,你又做出了离开森林的举动。