如何在带钥匙和门的谜题中找到最短路径
How to find the shortest path in a puzzle with keys and doors
我试过下面的代码，但它没有给我正确的答案。
这里是问题陈述。
Suppose you have a 2-D grid. Each point is either land or water. There
is also a start point and a goal.
There are now keys that open up doors. Each key corresponds to one
door.
Implement a function that returns the shortest path from the start to
the goal using land tiles, keys and open doors.
Data Representation
The map will be passed as an array of strings.
A map can have the following tiles.
0 = Water 1 = Land 2 = Start 3 = Goal uppercase = door
lowercase = key
The grid can be like this:
{{'0', '2', '1', '1', '1'},
{'0', '1', '0', '0', '1'},
{'0', '0', '0', '0', '1'},
{'0', '0', 'A', '0', '1'},
{'1', '1', 'a', '1', '1'},
{'1', 'b', '0', '0', 'B'},
{'1', '1', '0', '0', '1'},
{'0', '1', '0', '0', '3'}};
So the shortest path should be:
01->02->03->04->14->24->34->44->43->42->41->51->41->42->43->44->54->64->74
我的代码是这样的：
public class shortestPath {
static int shortest = Integer.MAX_VALUE;
static String path = "";
static ArrayList<ArrayList<int[]>> res = new ArrayList<ArrayList<int[]>>();
public static void main(String[] args) {
char[][] board = {{'0', '2', '1', '1', '1'},
{'0', '1', '0', '0', '1'},
{'0', '0', '0', '0', '1'},
{'0', '0', 'A', '0', '1'},
{'1', '1', 'a', '1', '1'},
{'1', 'b', '0', '0', 'B'},
{'1', '1', '0', '0', '1'},
{'0', '1', '0', '0', '3'}};
System.out.println(findShortest(board));
System.out.println(path);
}
public static int findShortest(char[][] board) {
if (board == null || board.length == 0 || board[0].length == 0) return 0;
int row = board.length;
int col = board[0].length;
int[] start = new int[2];
int[] end = new int[2];
int[][] visited = new int[row][col];
HashMap<Character, ArrayList<int[]>> hm = new HashMap<>();
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (board[i][j] == '2') {
start = new int[]{i, j};
}
if (board[i][j] == '3') {
end = new int[]{i, j};
}
if (Character.isUpperCase(board[i][j])) {
char key = Character.toLowerCase(board[i][j]);
if (hm.containsKey(key)) {
hm.get(key).add(new int[]{i, j});
} else {
ArrayList<int[]> al = new ArrayList<>();
al.add(new int[]{i, j});
hm.put(key, al);
}
board[i][j] = '0';
}
}
}
//HashSet<Character> hs = new HashSet<Character>();
//helper2(board, hs, start[0], start[1], row, col, 0, visited, new StringBuilder(), new ArrayList<int[]>(), res);
helper(board, hm, start[0], start[1], row, col, 0, visited, new StringBuilder());
return shortest;
}
public static void helper(char[][] board, HashMap<Character, ArrayList<int[]>> hm, int r, int c, int row, int col, int count, int[][] visited, StringBuilder sb) {
// System.out.println(r + " " + c);
visited[r][c] = visited[r][c] + 1;
sb.append(r).append(c).append("->");
if (board[r][c] == '3') {
System.out.println(count);
if (shortest > count) {
path = sb.deleteCharAt(sb.length() - 1).deleteCharAt(sb.length() - 1).toString();
sb.append("->");
shortest = count;
}
//return;
//shortest = Math.min(shortest, count);
}
if (Character.isLowerCase(board[r][c])) { // if this is the key;
if (hm.containsKey(board[r][c])) {
for (int[] i : hm.get(board[r][c])) {
board[i[0]][i[1]] = '1';
}
}
}
if (r + 1 < row && board[r + 1][c] != '0' && visited[r + 1][c] < 2) {
helper(board, hm, r + 1, c, row, col, count + 1, visited, sb);
}
if (c + 1 < col && board[r][c + 1] != '0' && visited[r][c + 1] < 2) {
helper(board, hm, r, c + 1, row, col, count + 1, visited, sb);
}
if (r - 1 >= 0 && board[r - 1][c] != '0' && visited[r - 1][c] < 2) {
helper(board, hm, r - 1, c, row, col, count + 1, visited, sb);
}
if (c - 1 >= 0 && board[r][c - 1] != '0' && visited[r][c - 1] < 2) {
helper(board, hm, r, c - 1, row, col, count + 1, visited, sb);
}
visited[r][c] = visited[r][c] - 1;
sb.delete(sb.length() - 4, sb.length());
if (Character.isLowerCase(board[r][c])) { // if this is the key;
if (hm.containsKey(board[r][c])) {
for (int[] i : hm.get(board[r][c])) {
board[i[0]][i[1]] = '0';
}
}
}
return;
}
}
您的问题是 visited 跟踪和锁门跟踪 （由 hm 变量管理，这是一个非常糟糕的名称，因为该名称无助于理解变量 is/does).
访问跟踪
你的小机器人经常来回走来走去。例如，如果将用于调试的打印语句插入到：
- 跟踪并打印尝试前进的总步数
- 只要找到更短的路径，就打印到达目标的最短路径
- 只要找到更长的路径，就打印尝试的最长路径
您会得到以下结果，其中 ! 表示行走的路径较长，* 表示找到目标的路径较短：
1: ! 01->
2: ! 01->11->
3: ! 01->11->01->
4: ! 01->11->01->11->
6: ! 01->11->01->02->03->
7: ! 01->11->01->02->03->04->
8: ! 01->11->01->02->03->04->14->
9: ! 01->11->01->02->03->04->14->24->
10: ! 01->11->01->02->03->04->14->24->34->
11: ! 01->11->01->02->03->04->14->24->34->44->
12: ! 01->11->01->02->03->04->14->24->34->44->34->
13: ! 01->11->01->02->03->04->14->24->34->44->34->44->
14: ! 01->11->01->02->03->04->14->24->34->44->34->44->43->
15: ! 01->11->01->02->03->04->14->24->34->44->34->44->43->42->
16: ! 01->11->01->02->03->04->14->24->34->44->34->44->43->42->43->
17: ! 01->11->01->02->03->04->14->24->34->44->34->44->43->42->43->42->
18: ! 01->11->01->02->03->04->14->24->34->44->34->44->43->42->43->42->32->
20: ! 01->11->01->02->03->04->14->24->34->44->34->44->43->42->43->42->41->51->
21: ! 01->11->01->02->03->04->14->24->34->44->34->44->43->42->43->42->41->51->61->
22: ! 01->11->01->02->03->04->14->24->34->44->34->44->43->42->43->42->41->51->61->71->
23: ! 01->11->01->02->03->04->14->24->34->44->34->44->43->42->43->42->41->51->61->71->61->
24: ! 01->11->01->02->03->04->14->24->34->44->34->44->43->42->43->42->41->51->61->71->61->71->
26: ! 01->11->01->02->03->04->14->24->34->44->34->44->43->42->43->42->41->51->61->71->61->51->41->
27: ! 01->11->01->02->03->04->14->24->34->44->34->44->43->42->43->42->41->51->61->71->61->51->41->40->
28: ! 01->11->01->02->03->04->14->24->34->44->34->44->43->42->43->42->41->51->61->71->61->51->41->40->50->
29: ! 01->11->01->02->03->04->14->24->34->44->34->44->43->42->43->42->41->51->61->71->61->51->41->40->50->60->
30: ! 01->11->01->02->03->04->14->24->34->44->34->44->43->42->43->42->41->51->61->71->61->51->41->40->50->60->50->
31: ! 01->11->01->02->03->04->14->24->34->44->34->44->43->42->43->42->41->51->61->71->61->51->41->40->50->60->50->60->
9577: * 01->11->01->02->03->04->14->24->34->44->43->42->41->51->61->71->61->51->41->42->43->44->54->64->74->
9611: ! 01->11->01->02->03->04->14->24->34->44->43->42->41->51->61->71->61->51->50->60->50->40->41->42->43->44->54->64->74->
9612: ! 01->11->01->02->03->04->14->24->34->44->43->42->41->51->61->71->61->51->50->60->50->40->41->42->43->44->54->64->74->64->
9613: ! 01->11->01->02->03->04->14->24->34->44->43->42->41->51->61->71->61->51->50->60->50->40->41->42->43->44->54->64->74->64->74->
9623: ! 01->11->01->02->03->04->14->24->34->44->43->42->41->51->61->71->61->51->50->60->50->40->41->42->43->44->34->24->14->04->03->02->
9901: * 01->11->01->02->03->04->14->24->34->44->43->42->41->51->61->51->41->42->43->44->54->64->74->
19141: ! 01->11->01->02->03->04->14->24->34->24->34->44->43->42->41->51->61->71->61->51->50->60->50->40->41->42->43->44->54->64->74->64->74->
53941: ! 01->11->01->02->03->04->14->04->14->24->34->24->34->44->43->42->41->51->61->71->61->51->50->60->50->40->41->42->43->44->54->64->74->64->
53942: ! 01->11->01->02->03->04->14->04->14->24->34->24->34->44->43->42->41->51->61->71->61->51->50->60->50->40->41->42->43->44->54->64->74->64->74->
145776: ! 01->11->01->02->03->02->03->04->14->04->14->24->34->24->34->44->43->42->41->51->61->71->61->51->50->60->50->40->41->42->43->44->54->64->74->64->
145777: ! 01->11->01->02->03->02->03->04->14->04->14->24->34->24->34->44->43->42->41->51->61->71->61->51->50->60->50->40->41->42->43->44->54->64->74->64->74->
158937: * 01->02->03->04->14->24->34->44->43->42->41->51->61->51->41->42->43->44->54->64->74->
前进总步数：390236
那条最长的路要来回走很多路：
01->11->
01->02->03->
02->03->04->14->
04->14->24->34->
24->34->44->43->42->41->51->61->71->61->
51->50->60->
50->40->41->42->43->44->54->64->74->
64->74->
那是浪费了很多步行。
锁门跟踪
重述您的逻辑：您最初将所有门更改为 0（水）。当您遇到一把钥匙时，您可以通过将棋盘值更改为 1（土地）来解锁适合该钥匙的所有门。回溯时，您将所有门更改回 0（水）。
现在看看您的代码得出的解决方案：
01->02->03->04->14->24->34->44->43->42->41->51->61->
51->41->42->43->44->54->64->74
问题是钥匙在 51，所以当代码在 秒 51 从那个解决方案回溯时，它会关上门，因此，当它回到 first 51 并尝试从那里直接走到目标时，门会关闭，即使你有钥匙。
那是因为你没有意识到你有两次钥匙。
解决方案
如果您只修复访问过的跟踪，您的代码将起作用，因为您不会两次踩到同一个键。
如果您只是修复锁定的门跟踪，即跟踪您拥有同一把钥匙的多个副本，您的代码将起作用，因为您不会再次过早地锁门。
但是，请考虑以下内容作为您修改后的解决方案：
- 如果实际上有不止一个相同的密钥怎么办？
- 不要重复访问一个位置，除非您已经拿到一把新钥匙。
- 如果您所走的路径已经比目前找到的最短目标路径还长，请不要继续走。
因此，一种不同的方法是考虑它在现实生活中的工作方式。当你找到钥匙时你不会打开门，因为 1) 你不一定知道门在哪里，以及 2) 你不能从你站的地方到达门。
相反，保留一个钥匙圈。当您遇到您没有的密钥时，将其添加到密钥环中。将新钥匙添加到钥匙圈还意味着您可以重新访问以前走过的区域。遇到一扇门，钥匙圈里有钥匙就可以穿过。
由于有 26 个可能的密钥，一个 32 位的 int 值可以作为您的密钥环。
查看 IDEONE 示例实现，它只需要 90 个步骤（而不是当前代码的 390236 个步骤）来检查所有 possible/relevant 个路径。
我试过下面的代码，但它没有给我正确的答案。
这里是问题陈述。
Suppose you have a 2-D grid. Each point is either land or water. There is also a start point and a goal.
There are now keys that open up doors. Each key corresponds to one door.
Implement a function that returns the shortest path from the start to the goal using land tiles, keys and open doors.
Data Representation
The map will be passed as an array of strings.
A map can have the following tiles.
0 = Water1 = Land2 = Start3 = Goaluppercase = doorlowercase = keyThe grid can be like this:
{{'0', '2', '1', '1', '1'}, {'0', '1', '0', '0', '1'}, {'0', '0', '0', '0', '1'}, {'0', '0', 'A', '0', '1'}, {'1', '1', 'a', '1', '1'}, {'1', 'b', '0', '0', 'B'}, {'1', '1', '0', '0', '1'}, {'0', '1', '0', '0', '3'}};So the shortest path should be: 01->02->03->04->14->24->34->44->43->42->41->51->41->42->43->44->54->64->74
我的代码是这样的：
public class shortestPath {
static int shortest = Integer.MAX_VALUE;
static String path = "";
static ArrayList<ArrayList<int[]>> res = new ArrayList<ArrayList<int[]>>();
public static void main(String[] args) {
char[][] board = {{'0', '2', '1', '1', '1'},
{'0', '1', '0', '0', '1'},
{'0', '0', '0', '0', '1'},
{'0', '0', 'A', '0', '1'},
{'1', '1', 'a', '1', '1'},
{'1', 'b', '0', '0', 'B'},
{'1', '1', '0', '0', '1'},
{'0', '1', '0', '0', '3'}};
System.out.println(findShortest(board));
System.out.println(path);
}
public static int findShortest(char[][] board) {
if (board == null || board.length == 0 || board[0].length == 0) return 0;
int row = board.length;
int col = board[0].length;
int[] start = new int[2];
int[] end = new int[2];
int[][] visited = new int[row][col];
HashMap<Character, ArrayList<int[]>> hm = new HashMap<>();
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (board[i][j] == '2') {
start = new int[]{i, j};
}
if (board[i][j] == '3') {
end = new int[]{i, j};
}
if (Character.isUpperCase(board[i][j])) {
char key = Character.toLowerCase(board[i][j]);
if (hm.containsKey(key)) {
hm.get(key).add(new int[]{i, j});
} else {
ArrayList<int[]> al = new ArrayList<>();
al.add(new int[]{i, j});
hm.put(key, al);
}
board[i][j] = '0';
}
}
}
//HashSet<Character> hs = new HashSet<Character>();
//helper2(board, hs, start[0], start[1], row, col, 0, visited, new StringBuilder(), new ArrayList<int[]>(), res);
helper(board, hm, start[0], start[1], row, col, 0, visited, new StringBuilder());
return shortest;
}
public static void helper(char[][] board, HashMap<Character, ArrayList<int[]>> hm, int r, int c, int row, int col, int count, int[][] visited, StringBuilder sb) {
// System.out.println(r + " " + c);
visited[r][c] = visited[r][c] + 1;
sb.append(r).append(c).append("->");
if (board[r][c] == '3') {
System.out.println(count);
if (shortest > count) {
path = sb.deleteCharAt(sb.length() - 1).deleteCharAt(sb.length() - 1).toString();
sb.append("->");
shortest = count;
}
//return;
//shortest = Math.min(shortest, count);
}
if (Character.isLowerCase(board[r][c])) { // if this is the key;
if (hm.containsKey(board[r][c])) {
for (int[] i : hm.get(board[r][c])) {
board[i[0]][i[1]] = '1';
}
}
}
if (r + 1 < row && board[r + 1][c] != '0' && visited[r + 1][c] < 2) {
helper(board, hm, r + 1, c, row, col, count + 1, visited, sb);
}
if (c + 1 < col && board[r][c + 1] != '0' && visited[r][c + 1] < 2) {
helper(board, hm, r, c + 1, row, col, count + 1, visited, sb);
}
if (r - 1 >= 0 && board[r - 1][c] != '0' && visited[r - 1][c] < 2) {
helper(board, hm, r - 1, c, row, col, count + 1, visited, sb);
}
if (c - 1 >= 0 && board[r][c - 1] != '0' && visited[r][c - 1] < 2) {
helper(board, hm, r, c - 1, row, col, count + 1, visited, sb);
}
visited[r][c] = visited[r][c] - 1;
sb.delete(sb.length() - 4, sb.length());
if (Character.isLowerCase(board[r][c])) { // if this is the key;
if (hm.containsKey(board[r][c])) {
for (int[] i : hm.get(board[r][c])) {
board[i[0]][i[1]] = '0';
}
}
}
return;
}
}
您的问题是 visited 跟踪和锁门跟踪 （由 hm 变量管理，这是一个非常糟糕的名称，因为该名称无助于理解变量 is/does).
访问跟踪
你的小机器人经常来回走来走去。例如，如果将用于调试的打印语句插入到：
- 跟踪并打印尝试前进的总步数
- 只要找到更短的路径，就打印到达目标的最短路径
- 只要找到更长的路径，就打印尝试的最长路径
您会得到以下结果，其中 ! 表示行走的路径较长，* 表示找到目标的路径较短：
1: ! 01->
2: ! 01->11->
3: ! 01->11->01->
4: ! 01->11->01->11->
6: ! 01->11->01->02->03->
7: ! 01->11->01->02->03->04->
8: ! 01->11->01->02->03->04->14->
9: ! 01->11->01->02->03->04->14->24->
10: ! 01->11->01->02->03->04->14->24->34->
11: ! 01->11->01->02->03->04->14->24->34->44->
12: ! 01->11->01->02->03->04->14->24->34->44->34->
13: ! 01->11->01->02->03->04->14->24->34->44->34->44->
14: ! 01->11->01->02->03->04->14->24->34->44->34->44->43->
15: ! 01->11->01->02->03->04->14->24->34->44->34->44->43->42->
16: ! 01->11->01->02->03->04->14->24->34->44->34->44->43->42->43->
17: ! 01->11->01->02->03->04->14->24->34->44->34->44->43->42->43->42->
18: ! 01->11->01->02->03->04->14->24->34->44->34->44->43->42->43->42->32->
20: ! 01->11->01->02->03->04->14->24->34->44->34->44->43->42->43->42->41->51->
21: ! 01->11->01->02->03->04->14->24->34->44->34->44->43->42->43->42->41->51->61->
22: ! 01->11->01->02->03->04->14->24->34->44->34->44->43->42->43->42->41->51->61->71->
23: ! 01->11->01->02->03->04->14->24->34->44->34->44->43->42->43->42->41->51->61->71->61->
24: ! 01->11->01->02->03->04->14->24->34->44->34->44->43->42->43->42->41->51->61->71->61->71->
26: ! 01->11->01->02->03->04->14->24->34->44->34->44->43->42->43->42->41->51->61->71->61->51->41->
27: ! 01->11->01->02->03->04->14->24->34->44->34->44->43->42->43->42->41->51->61->71->61->51->41->40->
28: ! 01->11->01->02->03->04->14->24->34->44->34->44->43->42->43->42->41->51->61->71->61->51->41->40->50->
29: ! 01->11->01->02->03->04->14->24->34->44->34->44->43->42->43->42->41->51->61->71->61->51->41->40->50->60->
30: ! 01->11->01->02->03->04->14->24->34->44->34->44->43->42->43->42->41->51->61->71->61->51->41->40->50->60->50->
31: ! 01->11->01->02->03->04->14->24->34->44->34->44->43->42->43->42->41->51->61->71->61->51->41->40->50->60->50->60->
9577: * 01->11->01->02->03->04->14->24->34->44->43->42->41->51->61->71->61->51->41->42->43->44->54->64->74->
9611: ! 01->11->01->02->03->04->14->24->34->44->43->42->41->51->61->71->61->51->50->60->50->40->41->42->43->44->54->64->74->
9612: ! 01->11->01->02->03->04->14->24->34->44->43->42->41->51->61->71->61->51->50->60->50->40->41->42->43->44->54->64->74->64->
9613: ! 01->11->01->02->03->04->14->24->34->44->43->42->41->51->61->71->61->51->50->60->50->40->41->42->43->44->54->64->74->64->74->
9623: ! 01->11->01->02->03->04->14->24->34->44->43->42->41->51->61->71->61->51->50->60->50->40->41->42->43->44->34->24->14->04->03->02->
9901: * 01->11->01->02->03->04->14->24->34->44->43->42->41->51->61->51->41->42->43->44->54->64->74->
19141: ! 01->11->01->02->03->04->14->24->34->24->34->44->43->42->41->51->61->71->61->51->50->60->50->40->41->42->43->44->54->64->74->64->74->
53941: ! 01->11->01->02->03->04->14->04->14->24->34->24->34->44->43->42->41->51->61->71->61->51->50->60->50->40->41->42->43->44->54->64->74->64->
53942: ! 01->11->01->02->03->04->14->04->14->24->34->24->34->44->43->42->41->51->61->71->61->51->50->60->50->40->41->42->43->44->54->64->74->64->74->
145776: ! 01->11->01->02->03->02->03->04->14->04->14->24->34->24->34->44->43->42->41->51->61->71->61->51->50->60->50->40->41->42->43->44->54->64->74->64->
145777: ! 01->11->01->02->03->02->03->04->14->04->14->24->34->24->34->44->43->42->41->51->61->71->61->51->50->60->50->40->41->42->43->44->54->64->74->64->74->
158937: * 01->02->03->04->14->24->34->44->43->42->41->51->61->51->41->42->43->44->54->64->74->
前进总步数：390236
那条最长的路要来回走很多路：
01->11->
01->02->03->
02->03->04->14->
04->14->24->34->
24->34->44->43->42->41->51->61->71->61->
51->50->60->
50->40->41->42->43->44->54->64->74->
64->74->
那是浪费了很多步行。
锁门跟踪
重述您的逻辑：您最初将所有门更改为 0（水）。当您遇到一把钥匙时，您可以通过将棋盘值更改为 1（土地）来解锁适合该钥匙的所有门。回溯时，您将所有门更改回 0（水）。
现在看看您的代码得出的解决方案：
01->02->03->04->14->24->34->44->43->42->41->51->61->
51->41->42->43->44->54->64->74
问题是钥匙在 51，所以当代码在 秒 51 从那个解决方案回溯时，它会关上门，因此，当它回到 first 51 并尝试从那里直接走到目标时，门会关闭，即使你有钥匙。
那是因为你没有意识到你有两次钥匙。
解决方案
如果您只修复访问过的跟踪，您的代码将起作用，因为您不会两次踩到同一个键。
如果您只是修复锁定的门跟踪，即跟踪您拥有同一把钥匙的多个副本，您的代码将起作用，因为您不会再次过早地锁门。
但是，请考虑以下内容作为您修改后的解决方案：
- 如果实际上有不止一个相同的密钥怎么办？
- 不要重复访问一个位置，除非您已经拿到一把新钥匙。
- 如果您所走的路径已经比目前找到的最短目标路径还长，请不要继续走。
因此，一种不同的方法是考虑它在现实生活中的工作方式。当你找到钥匙时你不会打开门，因为 1) 你不一定知道门在哪里，以及 2) 你不能从你站的地方到达门。
相反，保留一个钥匙圈。当您遇到您没有的密钥时，将其添加到密钥环中。将新钥匙添加到钥匙圈还意味着您可以重新访问以前走过的区域。遇到一扇门，钥匙圈里有钥匙就可以穿过。
由于有 26 个可能的密钥，一个 32 位的 int 值可以作为您的密钥环。
查看 IDEONE 示例实现，它只需要 90 个步骤（而不是当前代码的 390236 个步骤）来检查所有 possible/relevant 个路径。