Untitled

mail@pastecode.io avatar
unknown
plain_text
2 years ago
8.0 kB
1
Indexable
Never
import java.io.*;
import java.util.Scanner;

public class Maze {
    int rows;
    int cols;
    String[] map;
    int robotRow;
    int robotCol;
    int steps;

    public Maze(int n) {
        rows = n;
        cols = n;
        map = new String[rows];

        // Add the String to the map
        for (int i = 0; i < n; i++) {
            if (i == 0 || i == n - 1) {
                map[i] = new String(new char[n]).replace('\0', '.');
                continue;
            }

            map[i] = '.' + new String(new char[n - 2]).replace('\0', ' ') + '.';
        }

        robotRow = robotCol = 1;
        steps = 0;
    }

    public Maze() throws FileNotFoundException {
//        rows = 4;
//        cols = 5;
//        map = new String[rows];
//        map[0] = ".....";
//        map[1] = ".   X";
//        map[2] = ".   .";
//        map[3] = ".....";
//
//        robotRow = 2;
//        robotCol = 1;
//        steps = 0;

        File file = new File("D:\\RMIT\\data-structures-algorithms\\project\\src\\input.txt");
        Scanner scanner = new Scanner(file);

        rows = scanner.nextInt();
        cols = scanner.nextInt();
        robotRow = scanner.nextInt();
        robotCol = scanner.nextInt();
        scanner.nextLine();
        steps = 0;

        map = new String[rows];
        System.out.print(" ");
        for (int i = 0; i < cols; i++) {
            System.out.print(i);
        }
        System.out.println();

        for (int i = 0; i < rows; i++) {
            map[i] = scanner.nextLine();
            System.out.println(i + map[i]);
        }

        scanner.close();


    }

    /*
        INPUT:
        - String direction: The direction that the robot move
     */
    public String go(String direction) {
        if (!direction.equals("UP") &&
                !direction.equals("DOWN") &&
                !direction.equals("LEFT") &&
                !direction.equals("RIGHT")) {      // (1)
            // invalid direction
            steps++;                               // (1)
            return "false";                        // (1)
        }
        int currentRow = robotRow;                 // (1)
        int currentCol = robotCol;                 // (1)
        if (direction.equals("UP")) {              // (1)
            currentRow--;                          // (1)
        } else if (direction.equals("DOWN")) {     // (1)
            currentRow++;                          // (1)
        } else if (direction.equals("LEFT")) {     // (1)
            currentCol--;                          // (1)
        } else {                                   // (1)
            currentCol++;                          // (1)
        }


        // check the next position
        if (map[currentRow].charAt(currentCol) == 'X') { // (1)
            // Exit gate
            steps++;                               // (1)
            System.out.println("Steps to reach the Exit gate " + steps); // (1)
            return "win";                          // (1)
        } else if (map[currentRow].charAt(currentCol) == '.') { // (1)
            // Wall
            steps++;                               // (1)

            return "false";                        // (1)
        } else {                                   // (1)
            // Space => update robot location
            steps++;                               // (1)
            robotRow = currentRow;                 // (1)
            robotCol = currentCol;                 // (1)

            return "true";                         // (1)
        }
    }

    public static void main(String[] args) throws IOException {
        (new Robot()).navigate();         // (N * M) + (N * M)
    }
}



class Robot {
    static final int N = (int) (2e3 + 10);
    static final int[] dRow = new int[] {1, 0, -1, 0};
    static final int[] dCol = new int[] {0, 1, 0, -1};
    static final String[] dStr = new String[] {"DOWN", "RIGHT", "UP", "LEFT"};

    boolean[][] isObstacle, visited, deadEnd;
    int robotRow, robotCol;
    String result;

    public Robot() {
        isObstacle = new boolean[N][N];    // 2 * N * 2 * M
        visited = new boolean[N][N];       // 2 * N * 2 * M
        deadEnd = new boolean[N][N];       // 2 * N * 2 * M
        robotRow = N / 2;                  // 2 * N * 2 * M
        robotCol = N / 2;                  // 2 * N * 2 * M
        result = "";                       // 2 * N * 2 * M
    }

    /*
         INPUT:
         - Maze maze: The maze that the robot used for escaping
     */
   private void escapeTheDeadEndCell(Maze maze) {

       // If these cells are not available to move -> it is a deadEnd cell
       for (int i = 0; i < 4; i++) {                       // 4 * 1
           int nextRow = robotRow + dRow[i];               // 4 * 1
           int nextCol = robotCol + dCol[i];               // 4 * 1

           // Avoid the obstacle row or deadEnd cell
           if (isObstacle[nextRow][nextCol] || deadEnd[nextRow][nextCol]) {  // 4 * 1
               continue;                                  // 4 * 1
           }

           // Go to that cell
           result = maze.go(dStr[i]);                     // 4 * 1
           updateLocation(i);                             // 4 * 1
           return;                                       // 4 * 1
       }
   }

   /*
        INPUT:
        - Maze maze: The maze that the robot used for escaping
    */
    private boolean exploreTheNextCell(Maze maze) {
        // Search for the unvisited, not deadEnd cell
        for (int i = 0; i < 4; i++) {                  // 4 * 1
            int nextRow = robotRow + dRow[i];          // 4 * 1
            int nextCol = robotCol + dCol[i];          // 4 * 1


            // If the next cell is obstacle or visited
            if (isObstacle[nextRow][nextCol]) {        // 4 * 1
                continue;                              // 4 * 1
            }

            if (visited[nextRow][nextCol]) {           // 4 * 1
                continue;                              // 4 * 1
            }

            // Go to that cell
            result = maze.go(dStr[i]);                  // 4 * 1

            // If it is false
            if (result.equals("false")) {               // 4 * 1
                isObstacle[nextRow][nextCol] = true;    // 4 * 1
                visited[nextRow][nextCol] = true;       // 4 * 1
                continue;                               // 4 * 1
            }

            // Update the row
            updateLocation(i);                          // 4 * 1
            return true;                                // 4 * 1
        }

        return false;                                   // 4 * 1
    }

    /*
        INPUT - int directionIdx: The index of each direction storing in the array
     */
    public void updateLocation(int directionIdx) {
        robotRow = robotRow + dRow[directionIdx];          // (1)
        robotCol = robotCol + dCol[directionIdx];          // (1)
        visited[robotRow][robotCol] = true;                // (1)
    }

    public void navigate() throws FileNotFoundException {
        Maze maze = new Maze();                         // N * M
        visited[robotRow][robotCol] = true;             // O(1)

        while (!result.equals("win")) {                 // 2 * N * M
            if (exploreTheNextCell(maze)) {             // 2 * N * M
                continue;                               // 2 * N * M
            }

            // Set the current cell to be deadEnd
            deadEnd[robotRow][robotCol] = true;         // 2 * N * M

            // Escape the current dead-end
            escapeTheDeadEndCell(maze);                 // 2 * N * M
        }
    }
}