所以我一直在研究以下问题:
我埋葬了我的蓝宝石然后开始行走。我总是穿着沿着罗盘方向(北、南、东、西)的直线停了下来，我转了个90度的弯，继续往前走。我可能有遇到过我，但我不记得了。下面是米数我朝各个方向旅行。我现在迷路了，必须放弃这一切在我寻找出路的时候记录。我把这张纸条放在a下面在我最后的地点。也许某个幸运的冒险家会破译我的笔记，回到我的足迹去赚取宝藏。不幸的是,没有记录表明这张纸条是在废墟的什么地方发现的。相反,你必须写一个程序来找到宝藏。第一个输入line包含两个整数X Y，表示行数和废墟中的柱子。最多20行和50列。下一个X线条表示空间的网格图。一个句号"。是一个空方块。一个散列"#"是一个大圆石，标志着一个不能进入的正方形。下一行是整数N，表示直线路径的个数走了。最多20条路径。最后一行包含N个整数用空格分隔，显示连续的路径长度。5 10
# # # #........#
.#...##.#
...#....#
#### 8 2 4 2 2 2 5 2 1输出您的程序必须打印相同的地图，蓝宝石(S)和最终的位置标记的消息(F)的位置。同时，给每个转折点贴上标签使用连续的小写字母(如果同一点使用得更多)再打印一次，以备下次使用。)只有一个遵循列表中路径长度的路由。
# # # #<标题> b.e.a . . f# h1> #...##.#<标题> c.d # S.Fg # #
和我做了一个递归方法，从迷宫的每个开放位置开始检查每个方向，直到找到解决方案，但是问题的输出需要是有转弯的迷宫。
问题是，当我使用递归解决方案并编辑实际的char[][]映射时，它永远不知道哪条路径将导致实际完成，因此它将创建这样的输出:
d…d
…
cbabc
d…d
但是我希望它只显示一条路径，像这样:
d…
…abc
. .
…
这是我的不完全解:
import java.util.Scanner;
public class SapphireSearch {
private static int rs; // Row Size
private static int cs; // Column Size
private static int sr; // Save row (saves solution row)
private static int sc; // Save col (saves solution col)
private static Direction sd; // Save direction (saves solution dir)
private static char[][] map; // the maze to traverse
private static int n; // number of turns
private static int[] go; // length of the turns
public static void main(String[] args) {
getInput();
for (int r = 0; r < rs; r++)
for (int c = 0; c < cs; c++)
for (Direction d : Direction.values())
solve(sr = r, sc = c, sd = d, 0, false);
}
public static void solve(int r, int c, Direction d, int start,
boolean printing) {
if (isSolid(r, c))
return;
if (printing) {
if (start == 0)
map[r][c] = 'S';
else
map[r][c] = (char) (start - 1 + 'a');
if (start == n) {
map[r][c] = 'F';
return;
}
}
if (start == n - 1 && !printing) {
solve(sr, sc, sd, 0, true);
printArray(map);
System.exit(0);
}
int count = 0;
while (start < go.length && count < go[start]) {
count++;
r += d.dr;
c += d.dc;
if (isSolid(r, c))
return;
}
for (Direction t : d.turn())
solve(r, c, t, start + 1, printing);
}
public static boolean isSolid(int r, int c) {
return map[r][c] == '#';
}
public static void printArray(char[][] o) {
for (int r = 0; r < o.length; r++) {
for (int c = 0; c < o[r].length; c++)
System.out.print(o[r][c]);
System.out.println();
}
}
private static void getInput() {
Scanner s = new Scanner(System.in);
rs = s.nextInt();
cs = s.nextInt();
s.nextLine(); // clear buffer
map = new char[rs][cs];
for (int r = 0; r < rs; r++) {
int c = 0;
char[] f = s.nextLine().trim().toCharArray();
for (char t : f)
map[r][c++] = t;
}
n = s.nextInt();
go = new int[n];
for (int i = 0; i < n; i++)
go[i] = s.nextInt();
}
}
enum Direction {
// deltaR, deltaC
up(-1, 0), down(1, 0), left(0, -1), right(0, 1);
public int dr;
public int dc;
private Direction(int dr, int dc) {
this.dr = dr;
this.dc = dc;
}
public Direction[] turn() {
Direction[] out = new Direction[2];
switch (this) {
case up:
case down:
out[0] = left;
out[1] = right;
break;
case left:
case right:
out[0] = up;
out[1] = down;
}
return out;
}
}
问题是:在我的递归求解算法的基础上，打印解路径的最佳方法是什么(它不会打印出它试图采取的每条路径)?
当你进行递归搜索时，你需要建立你的回合列表(我在这里只是列出了方向，但你也可以存储一个带有坐标的对象)。
如果路径是(N,E,N,W,S)，然后在退出时保存。
要做到这一点，保留到目前为止的部分列表和每次递归调用复制到目前为止的列表并添加。
即:
n不西北失败
欧宁nes失败
nenw
等。
在最后，你可以返回完整的解决方案，或者如果你需要处理多个解决方案，你可以将完成的解决方案插入到一个最终结果列表中。
关键步骤是复制列表到目前为止，以使递归分支不会相互干扰。