Помогите, пожалуйста, реализовать следующий алгоритм.
Необходимо реализовать алгоритм для нахождения самого короткого пути из верхнего левого угла в правый нижний. Правый нижний элемент всегда равен 0. Массив всегда квадрат (например 3х3).
Двигаться по массиву можно только по направлению вниз или вправо. То, на какое количество "клеток" можно продвинутся определяет текущая позиция, так называемая сила прыжка (например если мы находимся на старте в точке [0][0] и соответствующий элемент 2, то мы можем сдвинутся на 2 вниз (D2) -> [2][0] или на 2 вправо (R2) -> [0][2]). Если сила прыжка выкидывает нас с поля (например массив 3х3 и мы ступили на клетку 5, то в любом случае мы вылетаем с поля в обоих направлениях), необходимо начать заново и искать другой путь.
Необходимо создать и реализовать алгоритм, который вычисляет путь, то есть порядок, в котором нужно прыгать/идти, чтобы достичь конца с минимально возможным количеством прыжков.
Таким образом путь будет [D1, R2, D1] - один ход вниз, два хода направо и один ход вниз
Моё решение, которое способно решить пример выше, но не справляется с решением массивов побольше (тест приложен)
public class Main {
int indexError = 0;
int shortestPathLen = Integer.MAX_VALUE;
List<String> shortestPath = new ArrayList<>();
List<List<String>> allPaths;
List<String> solution = new ArrayList<>();
public List<List<String>> findAllPaths(int[][] map, int D, int R) {
int currentPosition = map[D][R]; //D - down, R - right
if (currentPosition == 0) {
allPaths.add(solution);
return allPaths;
}
if (D + currentPosition <= indexError) {
solution.add("D" + currentPosition);
findAllPaths(map, D+currentPosition, R);
}
if (R + currentPosition <= indexError) {
solution.add("R" + currentPosition);
findAllPaths(map, D, R+currentPosition);
}
solution = new ArrayList<>();
return allPaths;
}
public List<String> findPath(int[][] map) {
indexError = map[0].length - 1;
shortestPathLen = Integer.MAX_VALUE;
allPaths = new ArrayList<>();
List<List<String>> l = findAllPaths(map, 0, 0);
for (List<String> path : l) {
if (path.size() < shortestPathLen) {
shortestPathLen = path.size();
shortestPath = path;
}
}
return shortestPath;
}
public static void main(String[] args) {
Main main = new Main();
// int len = 3;
// int[] array = {1, 2, 2,
// 2, 10, 1,
// 3, 2, 0}; // массив из примера
int len = 9;
int[] array =
{1, 10, 20, 1, 2, 2, 1, 2, 2,
1, 10, 1, 10, 2, 2, 1, 2, 2,
1, 10, 1, 1, 20, 2, 1, 2, 2,
2, 1, 10, 1, 1, 20, 1, 2, 2,
1, 2, 2, 10, 1, 1, 10, 2, 2,
2, 1, 1, 1, 10, 1, 1, 20, 2,
1, 2, 2, 1, 2, 10, 1, 1, 20,
1, 1, 1, 1, 2, 2, 10, 1, 1,
1, 2, 1, 1, 2, 2, 1, 1, 0};
int[][] map = new int[len][len];
int k = 0;
for (int i = 0; i < len; i++) {
for (int j = 0; j < len; j++) {
map[i][j] = array[k];
k++;
}
}
List result = main.findPath(map);
System.out.println("\n" + result + ", " + result.size() + " jumps");
// = must be [D1, D1, D1, D2, R2, D1, R2, D2, R2, R1, R1], 11 jumps
}}