Java Coding Test Course, Pathfinding

Problem Description

You need to find a path from the starting position (S) to the target position (G) in a given 2D grid. Some cells in the grid are blocked by obstacles (X), and you can move only up, down, left, or right.
We will use the BFS (Breadth-First Search) algorithm to solve this problem.

Example Input

                5 5
                S . . X G
                . X . X .
                . X . . .
                . . . X .
                . X . . E
            

Example Output

                7
            

The minimum path length from the starting position (S) to the target position (G) is 7.

Problem-Solving Strategy

We will use the BFS algorithm to solve this problem. BFS explores all nodes of a graph level by level.
By using this algorithm, you can quickly find the shortest path. By exploring all possible next positions from each location and reaching the target (G), the characteristics of BFS ensure that the shortest path is obtained.

Algorithm Steps

1. Convert the input data into a 2D array.
2. Find the starting position (S) and target position (G).
3. Use a queue (Q) to start the BFS search.
4. Check if the adjacent positions of the current location can be visited and add them to the queue.
5. If the target position (G) is reached, record the length of the path.
6. Return the shortest path once the BFS is complete.

Implementation in Java

Now, let’s implement the above algorithm in Java.

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

                public class PathFinding {
                    static class Position {
                        int x, y, distance;

                        Position(int x, int y, int distance) {
                            this.x = x;
                            this.y = y;
                            this.distance = distance;
                        }
                    }

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

                    public static int bfs(char[][] grid, int startX, int startY) {
                        Queue queue = new LinkedList<>();
                        boolean[][] visited = new boolean[grid.length][grid[0].length];

                        queue.offer(new Position(startX, startY, 0));
                        visited[startX][startY] = true;

                        while (!queue.isEmpty()) {
                            Position current = queue.poll();

                            if (grid[current.x][current.y] == 'G') {
                                return current.distance;
                            }

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

                                if (isValid(grid, newX, newY, visited)) {
                                    visited[newX][newY] = true;
                                    queue.offer(new Position(newX, newY, current.distance + 1));
                                }
                            }
                        }

                        return -1; // Path not found
                    }

                    private static boolean isValid(char[][] grid, int x, int y, boolean[][] visited) {
                        return x >= 0 && x < grid.length && y >= 0 && y < grid[0].length &&
                               grid[x][y] != 'X' && !visited[x][y];
                    }

                    public static void main(String[] args) {
                        char[][] grid = {
                            {'S', '.', '.', 'X', 'G'},
                            {'.', 'X', '.', 'X', '.'},
                            {'.', 'X', '.', '.', '.'},
                            {'.', '.', '.', 'X', '.'},
                            {'.', 'X', '.', '.', 'E'}
                        };

                        int startX = 0, startY = 0; // Position of S
                        int result = bfs(grid, startX, startY);

                        if (result != -1) {
                            System.out.println("Minimum path length to the target: " + result);
                        } else {
                            System.out.println("Cannot reach the target.");
                        }
                    }
                }
            

This code implements BFS to find the shortest path from the starting position (S) to the target (G) within the given grid. If a path is found, it outputs the minimum path length.

Conclusion

In this article, I explained how to solve pathfinding algorithm problems using Java. Solving problems using BFS is advantageous for finding the shortest path and is a topic frequently covered in various coding tests.
Through experience in solving algorithm problems, you can better prepare for coding tests. Practice more of these problems to improve your skills!