奇特的迷宫 ## 题目描述 如以下图(a)所示的15行、15列的迷宫(相当于n=8)，迷宫中每个位置可能为S（表示起始位置）、D（表示目标位置）、1～9的数字，且S和D各只有1个。对于1～9的数字，表示从当前位置出发，可以沿上、下、左、右方向走的方格数（多一个、少一个方格都不行）；图(b)演示的是，数字2表示可以沿上、下、左、右方向走2个方格，到达的位置用星号（*）表示。从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。 ## 样例输入 ```txt 8 1 42 322 2131 12213 231112 1S41223 13233411 2511322 121121 2122D 3112 121 23 1 0 ``` ## 样例输出 ```txt 5 ``` ## 提示 样例数据对应以上图(a)，从S位置出发，往上、右、右、右、下一共走5步，可到达D位置。