遗迹寻宝

题目背景

探险家小 R 进入了一座古代遗迹。遗迹的地面被划分成整齐的方格，有些格子堆着塌落的石块无法通过。遗迹里散落着若干宝物，小 R 必须把所有宝物都拿到手，再从出口离开。他想知道，最少要走多少步。

题目描述

遗迹是一个 $n$ 行 $m$ 列的网格，每个格子的含义如下：

• .：可以通行的空地；
• #：石块，无法通过；
• S：小 R 的出发点（恰好一处）；
• E：出口（恰好一处）；
• 宝物：第 $1 \sim 9$ 号宝物分别用字符 1 到 9 表示；如果宝物多于 $9$ 个，那么第 $10 \sim 15$ 号宝物分别用字符 A 到 F 表示。

小 R 每走一步，可以从当前格子移动到上、下、左、右四个方向中相邻的一个空格子（不能走出网格，也不能走进石块格）。

他必须经过所有宝物所在的格子（经过的顺序可以任意，每个宝物只需要经过一次），最后到达出口 E。同一个格子可以被经过多次。

请你求出最少需要的步数。如果无法做到（例如某个宝物与出发点不连通），输出 $-1$。

注意：宝物数量可能为 $0$，此时只需要从 S 走到 E。

输入格式

从标准输入读入数据。

第一行两个整数 $n, m$。

接下来 $n$ 行，每行一个长度为 $m$ 的字符串，描述遗迹的地图。保证恰好有一个 S 和一个 E。

输出格式

输出到标准输出。

一行一个整数，表示拿到所有宝物并到达出口所需的最少步数；若无法做到，输出 -1。

样例 1 输入

3 3
S1.
.#.
2.E

样例 1 输出

6

样例 1 解释

一种最优路线是：从 S 向右走到宝物 1（$1$ 步），再向左、向下、向下走到宝物 2（$3$ 步），最后向右、向右走到出口 E（$2$ 步），共 $1+3+2=6$ 步。中间的 (2,2) 是石块，不能穿过。

样例 2 输入

2 2
S#
#E

样例 2 输出

-1

样例 2 解释

没有宝物，但出发点与出口被石块隔开，无法到达出口。

数据范围

对全部测试数据，保证 $1 \le n, m \le 100$，$0 \le k \le 15$。

提交说明

本题使用标准输入输出。程序应从标准输入读入数据，并将答案输出到标准输出。