Java Coding Test Course, Exploring the Maze

Coding interviews and algorithm tests are common challenges for many candidates. One such problem, Maze Exploration, is a very popular algorithm problem that is suitable for learning search algorithms like BFS (Breadth-First Search) and DFS (Depth-First Search). In this article, we will examine the problem of exploring a maze using Java and explain a step-by-step approach to solve it.

Problem Description

In a given 2D array, 0 represents a space that can be traversed, and 1 represents a wall. The task is to find a path from the starting point to the destination point. If a path exists, print that path; if not, print “There is no path.”

Example Problem

    Input:
    [
        [0, 1, 0, 0, 0],
        [0, 1, 0, 1, 0],
        [0, 0, 0, 1, 0],
        [0, 1, 0, 0, 0],
        [0, 0, 0, 1, 0]
    ]
    Starting point (0, 0)
    Destination point (4, 4)

    Output:
    (0, 0) -> (1, 0) -> (2, 0) -> (2, 1) -> (2, 2) -> (3, 2) -> (4, 2) -> (4, 3) -> (4, 4)

Solution Process

1. Understand the Problem

First and foremost, it is essential to understand the problem accurately. In the 2D array representing the maze, you need to find a path from the starting point to the destination point without crossing any walls (1). In the example above, you should determine which path can lead from the starting point to the destination point.

2. Choose a Search Algorithm

Maze exploration can be solved using BFS or DFS. BFS is advantageous for finding the shortest path, while DFS is better suited for exploring paths deeply. Here, we will choose the BFS solution method.

3. Design the Algorithm

We will explore the path using the BFS algorithm in the following steps:

  1. Add neighboring points to the queue from the starting point.
  2. Remove points one by one from the queue and check if the point is the destination point.
  3. If it is not the destination point, add its neighboring points to the queue.
  4. If all paths have been explored and the destination point has not been reached, print “There is no path.”

4. Implement the Java Code

    import java.util.LinkedList;
import java.util.Queue;

public class MazeSolver {
    static class Point {
        int x, y;
        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    public static void main(String[] args) {
        int[][] maze = {
            {0, 1, 0, 0, 0},
            {0, 1, 0, 1, 0},
            {0, 0, 0, 1, 0},
            {0, 1, 0, 0, 0},
            {0, 0, 0, 1, 0}
        };
        
        findPath(maze, new Point(0, 0), new Point(4, 4));
    }

    static void findPath(int[][] maze, Point start, Point end) {
        int n = maze.length;
        int m = maze[0].length;
        boolean[][] visited = new boolean[n][m];
        Point[][] previous = new Point[n][m];

        Queue queue = new LinkedList<>();
        queue.offer(start);
        visited[start.x][start.y] = true;

        while (!queue.isEmpty()) {
            Point current = queue.poll();
        
            if (current.x == end.x && current.y == end.y) {
                printPath(previous, start, end);
                return;
            }

            for (int i = 0; i < 4; i++) {
                int nx = current.x + dx[i];
                int ny = current.y + dy[i];

                if (nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny] && maze[nx][ny] == 0) {
                    visited[nx][ny] = true;
                    previous[nx][ny] = current;
                    queue.offer(new Point(nx, ny));
                }
            }
        }

        System.out.println("There is no path.");
    }

    static void printPath(Point[][] previous, Point start, Point end) {
        StringBuilder path = new StringBuilder();
        for (Point at = end; at != null; at = previous[at.x][at.y]) {
            path.insert(0, String.format("-> (%d, %d) ", at.x, at.y));
        }
        System.out.println(path.substring(4)); // Remove the initial "-> "
    }
}

5. Code Explanation

The above code implements the BFS algorithm. It uses an inner class named Point to define (x, y) coordinates for queue and path tracking. Neighboring coordinates of the current position are added to the queue, and visited points are checked in the visited array to prevent duplicate searches. When the destination point is reached, the printPath method is called to print the path.

6. Code Execution Result

    (0, 0) -> (1, 0) -> (2, 0) -> (2, 1) -> (2, 2) -> (3, 2) -> (4, 2) -> (4, 3) -> (4, 4)

Conclusion

You have now learned how to solve the maze exploration problem. This algorithm is a useful technique that can be applied to various problems. Understanding the basics of search algorithms and implementing them in Java is a very rewarding experience. I hope this helps you in your coding test preparation!