//Show me how to write Java code which randomly generates a maze.

import java.util.Random;

public class MazeGenerator {
        private static final int ROWS = 10;
        private static final int COLS = 10;
        private static final int[][] MAZE = new int[ROWS][COLS];

        public static void main(String[] args) {
                // Initialize all cells as walls
                for (int row = 0; row < ROWS; row++) {
                        for (int col = 0; col < COLS; col++) {
                                MAZE[row][col] = 1;
                        }
                }

                // Create a random object
                Random rand = new Random();

                // Choose a random starting point
                int currentRow = rand.nextInt(ROWS);
                int currentCol = rand.nextInt(COLS);

                // Use depth-first search to generate the maze
                generateMaze(currentRow, currentCol);

                // Print the maze
                for (int row = 0; row < ROWS; row++) {
                        for (int col = 0; col < COLS; col++) {
                                System.out.print(MAZE[row][col] == 1 ? "# " : "  ");
                        }
                        System.out.println();
                }
        }

        private static void generateMaze(int row, int col) {
                // Mark the current cell as visited
                MAZE[row][col] = 0;

                // Create a random object
                Random rand = new Random();

                // While there is a neighboring cell to visit
                while (hasUnvisitedNeighbors(row, col)) {
                        // Choose a random neighboring cell
                        int[] neighbor = getRandomNeighbor(row, col);
                        int nextRow = neighbor[0];
                        int nextCol = neighbor[1];

                        // If the cell has not been visited yet
                        if (MAZE[nextRow][nextCol] == 1) {
                                // Remove the wall between the current cell and the next cell
                                removeWall(row, col, nextRow, nextCol);

                                // Move on to the next cell
                                generateMaze(nextRow, nextCol);
                        }
                }
        }

        private static boolean hasUnvisitedNeighbors(int row, int col) {
                return (row > 0 && MAZE[row - 1][col] == 1) ||
                                (row < ROWS - 1 && MAZE[row + 1][col] == 1) ||
                                (col > 0 && MAZE[row][col - 1] == 1) ||
                                (col < COLS - 1 && MAZE[row][col + 1] == 1);
        }

        private static int[] getRandomNeighbor(int row, int col) {
                Random rand = new Random();
                int[] neighbor = new int[2];
                int direction = rand.nextInt(4);

                if (direction == 0 && row > 0) {
                        neighbor[0] = row - 1;
                        neighbor[1] = col;
                } else if (direction == 1 && row < ROWS - 1) {
                        neighbor[0] = row + 1;
                        neighbor[1] = col;
                } else if (direction == 2 && col > 0) {
                        neighbor[0] = row;
                        neighbor[1] = col - 1;
                } else if (direction == 3 && col < COLS - 1) {
                        neighbor[0] = row;
                        neighbor[1] = col + 1;
                }
                return neighbor;
        }

        private static void removeWall(int row1, int col1, int row2, int col2) {
                if (row1 == row2) {
                        if (col1 > col2) {
                                MAZE[row1][col1 - 1] = 0;
                        } else {
                                MAZE[row1][col1 + 1] = 0;
                        }
                } else {
                        if (row1 > row2) {
                                MAZE[row1 - 1][col1] = 0;
                        } else {
                                MAZE[row1 + 1][col1] = 0;
                        }
                }
        }
}