Как найти кратчайший путь в головоломке с ключами и дверями
Я попробовал приведенный ниже код, но он не дал мне правильного ответа.
Вот постановка проблемы.
Предположим, у вас есть двумерная сетка. Каждая точка - это либо земля, либо вода. Существует также отправная точка и цель.
Теперь есть ключи, которые открывают двери. Каждый ключ соответствует одной двери.
Реализуйте функцию, которая возвращает кратчайший путь от начала до цели, используя плитки земли, ключи и открытые двери.
Представление данных
Карта будет передана в виде массива строк.
Карта может иметь следующие плитки.
0 = Water1 = Land2 = Start3 = Goaluppercase = doorlowercase = keyСетка может быть такой:
{{'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'}};Поэтому кратчайший путь должен быть: 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;
}
}
1 ответ
Ваша проблема - это сочетание плохой реализации visited отслеживание и отслеживание запертой двери (управляется hm переменная, которая является очень плохим именем, так как имя не помогает понять, что переменная является / делает).
Посещенное отслеживание
Ваш маленький робот часто ходит взад и вперед снова и снова. Например, если вы вставите оператор печати для отладки в:
- Отследить и распечатать общее количество выполненных шагов вперед
- Вывод кратчайшего пути к цели при обнаружении более короткого пути
- Выводить самую длинную попытку, когда найден более длинный путь
Вы получите следующий результат, где ! означает более длинный путь, и * означает более короткий путь к найденной цели:
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, он закрывает дверь, так что, когда он возвращается к первому 51 и пытается идти прямо к цели оттуда, дверь закрыта, даже если у вас есть ключ.
Это потому, что вы не понимаете, что у вас есть ключ дважды.
Решение
Если вы просто исправите посещенное отслеживание, ваш код будет работать, так как вы не нажмете один и тот же ключ дважды.
Если вы просто исправите отслеживание запертой двери, т. Е. Проследите, чтобы у вас было несколько копий одного и того же ключа, ваш код будет работать, так как вы не будете снова преждевременно закрывать двери.
Однако примите во внимание следующее для вашего исправленного решения:
- Что если на самом деле существует более одного и того же ключа?
- Не посещайте местоположение повторно, если вы не выбрали новый ключ.
- Не продолжайте идти, если вы находитесь на пути, который уже длиннее, чем самый короткий путь к цели, найденный до сих пор.
Итак, один из способов сделать это по-другому, это подумать о том, как это будет работать в реальной жизни. Вы не открываете дверь, когда находите ключ, потому что 1) вы не обязательно знаете, где находится дверь, и 2) вы не можете добраться до двери с того места, где вы стоите.
Вместо этого держите брелок для ключей. Когда вы встретите ключ, которого у вас нет, добавьте его в кольцо для ключей. Добавление нового ключа в кольцо для ключей также означает, что вы можете повторно посетить ранее пройденные районы. Когда вы сталкиваетесь с дверью, вы можете пройти через нее, если у вас есть ключ в кольце для ключей.
Поскольку существует 26 возможных ключей, int значение с 32 битами может быть вашим кольцом для ключей.
См. IDEONE для примера реализации, которая занимает всего 90 шагов (не 390236 шагов вашего текущего кода), чтобы проверить все возможные / соответствующие пути.