接受斌斌挑战的阿伟事人间之鉴

题目背景

阿伟对电子游戏很有兴趣。一天，他突然被传送到了一个电子游戏世界中。这个世界的神明斌斌告诉阿伟，如果他通过了这个世界的考验，他就可以获得 \(1000000\) 的 Steam 充值卡来买他最喜欢的新游戏，超勇的阿伟爽快地接受了这个挑战，但想通过考验不是这么简单。

题目描述

斌斌告诉阿伟，这个世界是一个 \(N * N (0 < N <= 100)\) 的世界，他可以在其中移动，移动一次消耗 1 个时间单位。

其中有 \(M (0<= M <=9)\) 种游戏挑战，阿伟需要按顺序通过这些挑战，才可以获得返回真实世界的钥匙，阿伟的游戏技术非常勇，所以他通过这些挑战几乎不需要时间。注意: 同一个编号的挑战算一种，可能会有多个，阿伟只需要通过其中一个就算通过这种。

但这个挑战不会这么简单，这个地图上还存在 \(x (0 <= x <= 5)\) 个考神杰哥的分身，如果阿伟经过他所在的区域，他就需要利用额外的 1 个时间单位去完成杰哥给他布置的习题。在一个地点通过之后，这个地方的杰哥分身就会消失了。

阿伟必须要从起点开始，依次通过游戏挑战，最终到达终点。阿伟是个急性子，他希望尽可能快的通过考验回到自己的世界，你需要帮他计算出通过挑战的最短用时。

输入格式

每次运行有多组输入数据，其中对于每一组:

第一行两个整数 \(N\)，\(M\)，表明这个世界是 \(N * N\) 大小的，其中有 \(M\) 种挑战(编号从 1 到 \(M\))。

接下来是一个 \(N * N\) 的矩阵，代表着世界地图。其中，每种字符代表的含义是:

|符号|含义|
|-|-|
|S |起点，可自由通过|
|D |出口，可自由通过|
|J |杰哥，可自由通过，但第一次通过需要额外用 1 个时间单位|
|. |空地，可以自由通过|
|数字x |第x种挑战，可自由通过|
|@ |墙壁，不可通过|

当读入 "0 0" 时，终止程序。

输出格式

一行。如果阿伟可以通过挑战，输出所用的最短时间; 否则输出"gg"。

样例输入

3 1
S@D
.J@
1@.
3 2
S@D
.J.
21.
0 0

样例输出

gg
8

来源

2014 ACM/ICPC Asia Regional Guangzhou Online