Введение

Возврат — это концепция, в которой сначала мы выбираем один путь и пытаемся найти ответ, если мы не находим ответ, возвращаемся и пробуем другой путь. Попробуем разобраться на простом примере.

Есть актер, который забыл свой телефон в любом из этих домов (A, B, C). Теперь ему нужно найти свой телефон, поэтому он начинает с дома A и проверяет, доступен ли его телефон. Он не нашел свой телефон в доме А, поэтому он возвращается (возвращается туда, откуда начал). Теперь он идет в дом Б ищет свой телефон, здесь он нашел свой телефон, вернулся и говорит, что нашел свой телефон. Он не пошел в дом С.

Теперь о том случае, когда актер должен найти все возможные пути от своего дома до места съемок. Ему предстоит пройти все пути от своего дома один за другим до места съемок. Если он нашел какой-либо путь, который ведет к месту, которое он регистрирует/помнит, вернулся, выбирает следующий путь и так далее... и в конце он находит все возможные пути, ведущие к месту съемок от его дома.

Определение из Википедии: обратный поиск может быть определен как общий алгоритмический метод, который рассматривает поиск всех возможных комбинаций для решения вычислительной задачи. >

Проблема: крыса в лабиринте

Вам дан лабиринт N*N с крысой, помещенной в лабиринт[0][0]. Найдите, существует ли какой-либо путь, по которому крыса может пройти, чтобы добраться до места назначения, например, лабиринт[N-1][N-1]. Крыса может двигаться в любом направлении (влево, вправо, вверх и вниз). поэтому мы должны найти путь, чтобы добраться до конца с самого начала. В вопросе дан массив 2d, в котором 1 означает, что мы можем пройти через эту ячейку, а 0 (ноль) означает, что она заблокирована. Для каждого блока мышь может двигаться вверх, вниз, влево, вправо.

Решение:

Итак, для этого нам дана матрица N*N. Поэтому мы создаем новый 2d-массив, чтобы отслеживать, проходим ли мы путь или нет.

Итак, мы создаем функцию с параметром лабиринт(двухмерный массив уже заданного пути), строка(для отслеживания строк), столбец(для отслеживания столбцов) и массив(новый массив для отслеживания пройденного пути).

Итак, проверяем, сколькими способами нам нельзя двигаться в клетку?

  1. если строка‹0
  2. если строка ›= длина лабиринта
  3. столбец‹0
  4. col ›= лабиринт.длина
  5. лабиринт[строка][столбец] == 0
  6. стрелка[строка][столбец] == 1

если какой-либо из вариантов (от 1 до 6) верен, мы просто возвращаемся.

если нет в опциях (от 1 до 6), то это допустимая ячейка, и мы можем перейти к ячейке/блоку.

поэтому мы делаем ячейки массива пройденными. (arr[row][col] = 1).

Теперь проверим, доходим ли мы до конца или нет, если мы доходим до конца, мы печатаем путь массива.

Теперь важная часть рекурсии:

от каждого блока мы должны двигаться в четырех направлениях вверх, влево, вниз, вправо.

  1. для перемещения вверх — (строка-1, столбец)
  2. двигаться влево — (строка, столбец+1)
  3. для перемещения вниз — (строка+1, столбец)
  4. двигаться вправо — (строка, столбец-1)

поэтому мы вызываем рекурсию для всех четырех направлений, если возможно двигаться в вызываемой рекурсии, мы переходим к следующему блоку/ячейке и вызываем рекурсию в следующей ячейке/блоке во время возврата (нет доступного пути, возвращающегося в рекурсии ), то мы движемся в следующем направлении. Таким образом, мы проверяем все возможные направления для каждого возможного блока/ячейки.

Java-код:

public static void improveRatInMaze(int [][]maze,int row,int col,int[][]arr){
    // we check, how many ways we are not allowed to move to the cell?
    if(row<0 || row>=maze.length || col<0 || col>=maze.length || maze[row][col]==0 || arr[row][col]==1){
        return;
    }
    // if not in any of the options(1 to 6), then that is a valid cell, and we can move to the cell/block.

    //so we make array cells as traveled.(arr[row][col] = 1).
    arr[row][col] = 1;
    // check whether we reach the end cell/block.
    if(row==maze.length-1 && col==maze.length-1){
        // if we reach end print all possible path.
        for (int[] ints : arr) {
            for (int anInt : ints) {
                System.out.print(anInt + " ");
            }
        }
        System.out.println();
        //making the array cell not traveled.
        arr[row][col]=0;
        return;
    }
    // calling recursion on all four direction

    // UP
    improveRatInMaze(maze,row-1,col,arr);
    // Down
    improveRatInMaze(maze,row+1,col,arr);
    // Right
    improveRatInMaze(maze,row,col+1,arr);
    // Left
    improveRatInMaze(maze,row,col-1,arr);
    
    // if not reach the end cell/block for certain path
    // making the array cell not traveled.
    arr[row][col] = 0;
}

Спасибо. Пожалуйста, комментируйте и хлопайте в ладоши.