deyanmalinov

Backtraking/Find All Paths in a Labyrinth

May 6th, 2022 (edited)
357
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 1.64 KB | None | 0 0
  1. public class Main {
  2.     static List<Character> path = new ArrayList<>();
  3.     public static void main(String[] args) {
  4.         Scanner scan = new Scanner(System.in);
  5.         int rows = Integer.parseInt(scan.nextLine());
  6.         int cols = Integer.parseInt(scan.nextLine());
  7.         char[][] maze = new char[rows][cols];
  8.  
  9.  
  10.         for (int row = 0; row < rows; row++) {
  11.             maze[row] = scan.nextLine().toCharArray();
  12.         }
  13.  
  14.         findPath(maze, 0, 0, ' ');
  15.  
  16.         for (char [] ch : maze) {
  17.             System.out.println(Arrays.toString(ch));
  18.         }
  19.     }
  20.     private static void findPath(char[][] maze, int row, int col, char direction){
  21.         if (!isInBounds(maze, row, col)){
  22.             return;
  23.         }
  24.         if (maze[row][col] == 'x'){
  25.             return;
  26.         }
  27.         if (maze[row][col] == '*'){
  28.             return;
  29.         }
  30.  
  31.         path.add(direction);
  32.  
  33.         if (maze[row][col] == 'e'){
  34.             printPath();
  35.             return;
  36.         }
  37.  
  38.         maze[row][col] = 'x';
  39.  
  40.         findPath(maze, row, col - 1,'L');
  41.         findPath(maze, row + 1, col,'D');
  42.         findPath(maze, row, col + 1,'R');
  43.         findPath(maze, row - 1 , col, 'U');
  44.  
  45.         maze[row][col] = '-';
  46.  
  47.         path.remove(path.size() - 1);
  48.  
  49.     }
  50.     private static void printPath(){
  51.         path.remove(0);
  52.         for (Character character : path) {
  53.             System.out.print(character);
  54.         }
  55.         System.out.println();
  56.     }
  57.     private static boolean isInBounds(char[][] maze, int rows, int cols){
  58.         return rows < maze.length && rows >= 0 && cols < maze[rows].length && cols >= 0;
  59.     }
  60. }
Add Comment
Please, Sign In to add comment