题目描述

你发现你身处一片森林，你需要找到出口逃离这里。但是在森林中还有其他人和很多树木。他们会给你造成阻碍。

所有人都会沿向终点的最短路径行进。

输入格式

输入 $n$ 和 $m$，$1\le n,m\le 1000$，接下来输入一张 $n \times m$ 的二维地图，地图中只包含以下元素：

• T：一棵树，不能通行。
• S：你的起始位置，在地图中只有一个。
• E：出口，在地图中也只有一个。
• $0 \sim 9$ 中的一个数字：这个位置上的人数，可以从该点通过。

输出格式

输出在你到达出口前，到达出口的人数（包括与你同时到达终点的人）。

5 7
000E0T3
T0TT0T0
010T0T0
2T0T0T0
0T0S000

3

1 4
SE23

2