CF329B.Biridian Forest

You're a mikemon breeder currently in the middle of your journey to become a mikemon master. Your current obstacle is go through the infamous Biridian Forest.

The forest

The Biridian Forest is a two-dimensional grid consisting of r rows and c columns. Each cell in Biridian Forest may contain a tree, or may be vacant. A vacant cell may be occupied by zero or more mikemon breeders (there may also be breeders other than you in the forest). Mikemon breeders (including you) cannot enter cells with trees. One of the cells is designated as the exit cell.

The initial grid, including your initial position, the exit cell, and the initial positions of all other breeders, will be given to you. Here's an example of such grid (from the first example):

Moves

Breeders (including you) may move in the forest. In a single move, breeders may perform one of the following actions:

• Do nothing.
• Move from the current cell to one of the four adjacent cells (two cells are adjacent if they share a side). Note that breeders cannot enter cells with trees.
• If you are located on the exit cell, you may leave the forest. Only you can perform this move — all other mikemon breeders will never leave the forest by using this type of movement.

After each time you make a single move, each of the other breeders simultaneously make a single move (the choice of which move to make may be different for each of the breeders).

Mikemon battle

If you and t (t > 0) mikemon breeders are located on the same cell, exactly t mikemon battles will ensue that time (since you will be battling each of those t breeders once). After the battle, all of those t breeders will leave the forest to heal their respective mikemons.

Note that the moment you leave the forest, no more mikemon battles can ensue, even if another mikemon breeder move to the exit cell immediately after that. Also note that a battle only happens between you and another breeders — there will be no battle between two other breeders (there may be multiple breeders coexisting in a single cell).

Your goal

You would like to leave the forest. In order to do so, you have to make a sequence of moves, ending with a move of the final type. Before you make any move, however, you post this sequence on your personal virtual idol Blog. Then, you will follow this sequence of moves faithfully.

Goal of other breeders

Because you post the sequence in your Blog, the other breeders will all know your exact sequence of moves even before you make your first move. All of them will move in such way that will guarantee a mikemon battle with you, if possible. The breeders that couldn't battle you will do nothing.

Your task

Print the minimum number of mikemon battles that you must participate in, assuming that you pick the sequence of moves that minimize this number. Note that you are not required to minimize the number of moves you make.

你是一名米可梦训练师，目前正在成为米可梦大师的旅途中。你当前面临的挑战是穿越臭名昭著的比里迪安森林（Biridian Forest）。

森林结构

比里迪安森林是一个由 $r$ 行和 $c$ 列组成的二维网格。森林中的每个格子要么是一棵树，要么是空地。空地格子上可以有零个或多个米可梦训练师（除你之外，森林中可能还有其他训练师）。米可梦训练师（包括你）不能进入有树的格子。其中某个格子被指定为出口格子。

初始网格（包括你的起始位置、出口格子，以及所有其他训练师的初始位置）将提供给你。以下是一个初始网格示例（来自第一个样例）：

移动规则

训练师（包括你）可以在森林中移动。在一次移动中，训练师可执行下列操作之一：

• 什么都不做；
• 从当前格子移动到四个相邻格子之一（两个格子相邻当且仅当它们共享一条边）。注意：训练师不能进入有树的格子；
• 若你位于出口格子上，则你可以离开森林。只有你可以执行该操作——所有其他米可梦训练师永远不会通过此类移动离开森林。

每次你完成一次移动后，其余所有训练师将同时各自执行一次移动（每位训练师所选动作可以不同）。

米可梦对战

若你与 $t$（$t > 0$）名米可梦训练师处于同一格子，则该时刻将恰好发生 $t$ 场米可梦对战（因为你将分别与这 $t$ 名训练师各对战一次）。对战结束后，这 $t$ 名训练师将全部离开森林，以治疗各自的米可梦。

注意：一旦你离开森林，便不再可能发生任何米可梦对战，即使另一名训练师紧接着就移动到出口格子亦然。此外，对战只发生在你与其他训练师之间——任意两名其他训练师之间不会发生对战（即一个格子上可能共存多名其他训练师）。

你的目标

你想离开森林。为此，你必须执行一系列移动，且该序列的最后一次移动必须是上述第三种类型（即在出口格子上离开森林）。然而，在你执行任何移动之前，你需先将该移动序列发布在你的个人虚拟偶像博客（Blog）上，之后你将严格遵循该序列行动。

其他训练师的目标

由于你在博客上发布了该序列，其他所有训练师甚至在你迈出第一步之前就已完全知晓你的精确移动序列。他们将全部采取策略性移动，以尽可能确保与你发生米可梦对战（若可行）；无法与你对战的训练师则选择“什么都不做”。

你的任务

假设你选择能最小化自身参与的米可梦对战次数的移动序列，请输出你必须参与的最少对战次数。注意：你无需最小化你自己的移动步数。

The first line consists of two integers: r and c (1 ≤ r, c ≤ 1000), denoting the number of rows and the number of columns in Biridian Forest. The next r rows will each depict a row of the map, where each character represents the content of a single cell:

• 'T': A cell occupied by a tree.
• 'S': An empty cell, and your starting position. There will be exactly one occurence of this in the map.
• 'E': An empty cell, and where the exit is located. There will be exactly one occurence of this in the map.
• A digit (0-9): A cell represented by a digit X means that the cell is empty and is occupied by X breeders (in particular, if X is zero, it means that the cell is not occupied by any breeder).

It is guaranteed that it will be possible for you to go from your starting position to the exit cell through a sequence of moves.

第一行包含两个整数：$r$ 和 $c$（$1 \leq r, c \leq 1000$），分别表示 Biridian 森林的行数与列数。接下来的 $r$ 行每行描述地图的一行，其中每个字符代表一个单元格的内容：

• 'T'：一棵树占据的单元格。
• 'S'：一个空单元格，也是你的起始位置。地图中恰好出现一次该字符。
• 'E'：一个空单元格，也是出口所在位置。地图中恰好出现一次该字符。
• 一个数字（0–9）：若某单元格用数字 $X$ 表示，则该单元格为空，且有 $X$ 个驯兽师占据（特别地，若 $X = 0$，则表示该单元格未被任何驯兽师占据）。

保证存在一条从你的起始位置到出口单元格的可行移动路径。

A single line denoted the minimum possible number of mikemon battles that you have to participate in if you pick a strategy that minimize this number.

一行，表示如果你选择一种能最小化该数值的策略，则你必须参与的米可梦对战的最少场数。

The following picture illustrates the first example. The blue line denotes a possible sequence of moves that you should post in your blog:

The three breeders on the left side of the map will be able to battle you — the lone breeder can simply stay in his place until you come while the other two breeders can move to where the lone breeder is and stay there until you come. The three breeders on the right does not have a way to battle you, so they will stay in their place.

For the second example, you should post this sequence in your Blog:

Here's what happens. First, you move one cell to the right.

Then, the two breeders directly to the right of the exit will simultaneously move to the left. The other three breeder cannot battle you so they will do nothing.

You end up in the same cell with 2 breeders, so 2 mikemon battles are conducted. After those battles, all of your opponents leave the forest.

Finally, you make another move by leaving the forest.

下图展示了第一个样例。蓝色线条表示你应该在博客中发布的可能的移动序列：

地图左侧的三位培育者能够与你对战——其中单独一位培育者可原地静候，直至你抵达；另外两位培育者则可先移动至该单独培育者所在位置，并静候你抵达。而地图右侧的三位培育者无法与你对战，因此将始终停留在原地。

对于第二个样例，你应该在博客中发布如下序列：

具体过程如下：首先，你向右移动一格。

接着，出口正右侧的两位培育者将同时向左移动。其余三位培育者无法与你对战，因此不采取任何行动。

最终，你与这两位培育者处于同一格内，因此将进行两场小精灵对战。对战结束后，所有对手均离开森林。

最后，你再执行一次移动，离开森林。