1911: 奇特的迷宫

迷宫中每个位置可能为S（表示起始位置）、D（表示目标位置）、1～9的数字，且S和D各只有1个。对于1～9的数字n，表示从当前位置出发，可以沿上、下、左、右方向走n步（多一步、少一步都不行），如图(b)所示。从S出发，可以沿上、下、左、右方向走1步。现在要求从S到D的最少步数。

输入文件中包含多个测试数据。每个测试数据的第1行为一个整数n，2≤n≤10，表示迷宫的大小为2n-1行、2n-1列。接下来有2n-1行，为每行各位置上的数字（或者为S、D），第1行有1个字符，第2行有2个字符，…，第n行有n个字符，第n+1行有n-1个字符，…，第2n-1行有1个字符。输入文件中最后一行为0，表示测试数据结束。

对输入文件中的每个测试数据，如果能从S走到D，则输出最少步数；否则（即从S走不到D），则输出0。

4
1
23
1S4
1323
21D
23
2
8
1
42
322
2131
12213
231112
1S41223
13233411
2511322
121121
2122D
3112
121
23
1
0

2
5