Алгоритм обхода лабиринта с использованием рекурсии

Question

Я пытаюсь пройти лабиринт, используя рекурсию для класса. Мне предоставили шаблон и просто нужно ввести процесс прохождения лабиринта; Я не разрешается изменять код в любом случае, кроме того, что закупорки после этого:

public boolean mazeTraversal (char maze2[][], int x, int y) 

Я действительно трудное время с этим и не знаю, что мне не хватает. Я все еще и ultra noob, когда речь идет о Java и программировании в целом. Любые подсказки будут высоко оценены.

// Exercise 18.20 Solution: Maze.java 
//Program traverses a maze. 
import java.util.Scanner; 

package maze; 


public class Maze { 
public static void main(String args[]) 
{ 

} 
/** 
* @param args the command line arguments 
*/ 

static final int DOWN = 0; 
static final int RIGHT = 1; 
static final int UP = 2; 
static final int LEFT = 3; 
static final int X_START = 2; 
static final int Y_START = 0; 
static final int move = 0; 
static char maze [][] = 
{ { '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#' }, 
    { '#', '.', '.', '.', '#', '.', '.', '.', '.', '.', '.', '#' }, 
    { 'S', '.', '#', '.', '#', '.', '#', '#', '#', '#', '.', '#' }, 
    { '#', '#', '#', '.', '#', '.', '.', '.', '.', '#', '.', '#' }, 
    { '#', '.', '.', '.', '.', '#', '#', '#', '.', '#', '.', 'F' }, 
    { '#', '#', '#', '#', '.', '#', '.', '#', '.', '#', '.', '#' }, 
    { '#', '.', '.', '#', '.', '#', '.', '#', '.', '#', '.', '#' }, 
    { '#', '#', '.', '#', '.', '#', '.', '#', '.', '#', '.', '#' }, 
    { '#', '.', '.', '.', '.', '.', '.', '.', '.', '#', '.', '#' }, 
    { '#', '#', '#', '#', '#', '#', '.', '#', '#', '#', '.', '#' }, 
    { '#', '.', '.', '.', '.', '.', '.', '#', '.', '.', '.', '#' }, 
    { '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#' } }; 
    static Scanner scanner = new Scanner (System.in); 

     //method calls mazeTraversal with correct starting point and direction 
     public void traverse() 
     { 
     boolean result = mazeTraversal (maze, X_START, Y_START); 

     if (!result) 
     System.out.println ("Maze has no solution."); 
     } //end method traverse 
     //traverse maze recursively 
     public boolean mazeTraversal (char maze2[][], int x, int y) 
     { 
     // TO BE COMPLETED 
     //check for boundaries 
     if (x < 0 || y < 0 || x >= maze.length || y >= maze[0].length) 
     return false; 
     //base case - did I reach finish? 
     if(maze [x][y] == 'F') 
     return true; 
     //check if Valid point 
     if (maze [x][y] != '.' || maze[x][y] != 'S') 
     // hit a wall, not valid 
     return false; 
     //must be on a path, may be the right path 
     //breadcrumb 
     maze [x][y] = '.'; 
     //up 
     if (mazeTraversal (x+1,y)) 

     { 
     maze [x][y]= '#'; 
     return true; 
     } 
     if (mazeTraversal (x,y+1)) 
     { 
     maze [x][y] = '#'; 
     return true; 
     } 
     // can't go any further 
     return false; 
     } 
     } 

     //draw maze 
     public void printMaze() 
     { 
     // for each space in maze 
     for (int row = 0; row < maze.length; row++) 
     { 
     for (int column = 0; column < maze [row].length; column++) 
     { 
     if (maze [x][y] == '0') 
     System.out.print ("."); 

     else 
     System.out.print (" " + maze [x][y]); 
     } 
     System.out.println(); 
     } 
     System.out.println(); 
     } 
     } 

Answer 1

На любой данный момент, вы будете иметь 4 направления, чтобы двигаться, если вы или не на краю, с данным ограничением, что вы не можете двигаться по диагонали или через стены. Начните с пустой матрицы 2x2, и на каждом шаге вы можете приблизиться к начальной точке, отметьте «1», потому что она занимает один шаг.

После этого отметьте «2» смежными юридическими шагами, которые еще не имеют номера.

Затем отметьте «3» всем смежным юридическим шагам рядом с 2s, которые уже не имеют номера.

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

Указывая только номер, который еще не был назначен, это позволит избежать обратного хода или наступить на шаг, который уже был достигнут ранее. Это гарантирует, что матрица будет заполнена «наилучшими возможными маршрутами».

(Смотрите, где рекурсия приходит? :))