How to correctly implement breadth-first search (BFS) path finding in a two-dimensional maze

This article explains in detail the typical reasons why BFS fails to find the target value 9 in the 0/1/9 maze. It focuses on the problem of hash conflicts caused by not adding delimiters to the coordinate string hash keys, and provides a robust and reusable BFS implementation solution.

Using BFS to find targets (such as the number 9) in a two-dimensional maze is a classic scenario for getting started with the algorithm, but a seemingly small implementation detail— the way the coordinate hash key is constructed —often leads to early termination of the search, missing paths, and even infinite loops. The core flaw of the above code is:

 String ps = Integer.toString(px) Integer.toString(py);

This way of writing maps both coordinates (1, 10) and (11, 0) to the string "110", causing a hash conflict : once (1, 10) is marked as visited, (11, 0) will be mistakenly skipped, even though it leads to the target. This is a typical "delimiter-free coordinate splicing" trap.

✅ The correct approach is to introduce a unique, parsable delimiter , such as colon::

 String key = px ":" py; // Recommended: concise, clear semantics, unambiguous // or more secure formatting (to prevent interference from negative or large numbers, but the coordinates of this question are non-negative, optional)
// String key = String.format("%d,%d", px, py);

In addition, there are many points in the original code that can be optimized and corrected:

✅ Recommended refactoring points

1. Use Set instead of Map
   HashMap is essentially a simulated collection, which only adds redundancy. Directly using Set (or custom immutable coordinate class) is more semantically accurate and type-safe:

    //Define lightweight coordinate class (need to rewrite equals & hashCode!)
   static class Pos {
       final int x, y;
       Pos(int x, int y) { this.x = x; this.y = y; }
       @Override public boolean equals(Object o) {
           if (!(o instanceof Pos)) return false;
           Pos p = (Pos) o;
           return x == px && y == py;
       }
       @Override public int hashCode() { return Objects.hash(x, y); }
   }
   
   // Use Set to manage visited nodes Set<pos> visited = new HashSet();</pos>

2. Avoid static variables polluting state
   In the original code, q and map_seen are public static, causing multiple calls to interfere with each other and make threads unsafe. Should be changed to local variables or encapsulated as instance methods:

    public static List<int> searchPath(int[][] maze, int startX, int startY) {
       if (maze == null || maze.length == 0 || maze[0].length == 0) 
           return Collections.emptyList();
   
       Queue<pos> queue = new LinkedList();
       Set<pos> visited = new HashSet();
       Map<pos pos> parent = new HashMap(); // Used for backtracking path Pos start = new Pos(startX, startY);
       queue.offer(start);
       visited.add(start);
   
       int[][] dirs = {{1,0}, {-1,0}, {0,1}, {0,-1}}; // right, left, bottom, top while (!queue.isEmpty()) {
           Pos cur = queue.poll();
   
           // Check if the target is reached if (cur.y &gt;= 0 &amp;&amp; cur.y = 0 &amp;&amp; cur.x </pos></pos></pos></int>

3. Robustness enhancements to isFree()
   The original method ensures that the boundary is valid before checking maze[y][x], but it is recommended to separate boundary judgment and value judgment to improve readability and debugging friendliness:

    static boolean isFree(int[][] maze, int x, int y) {
       if (x = maze[0].length || y = maze.length) 
           return false;
       return maze[y][x] == 0 || maze[y][x] == 9;
   }

4. Path reconstruction example
   Use the parent mapping to build the path in reverse (from the target to the starting point), and then reverse the output:

    static List<int> reconstructPath(Map<pos pos> parent, Pos start, Pos target) {
       List<int> path = new ArrayList();
       for (Pos p = target; p != null; p = parent.get(p)) {
           path.add(new int[]{px, py});
       }
       Collections.reverse(path);
       return path;
   }</int></pos></int>

⚠️ Summary of precautions

• ❌Never use x "" y as a hash key for two-dimensional coordinates - there is inherent ambiguity;
• ✅Use Set first and define equals/hashCode correctly , which is more efficient and safer than string keys;
• ? Avoid static collections/queues : BFS is a one-time search process and the state should be isolated;
• ? Debugging tips : print the current coordinates and maze[y][x] value after queue.poll() to quickly verify whether the target grid is skipped;
• ? Extensibility tip : If you need to support more states besides obstacles (1), open space (0), and target (9), isFree() can be abstracted into a strategy interface.

Through the above modifications, your BFS will truly be "complete" and "deterministic" - as long as the target is reachable, it will be found; and the path will be the shortest, logically clear, and easy to maintain.

The above is the detailed content of How to correctly implement breadth-first search (BFS) path finding in a two-dimensional maze. For more information, please follow other related articles on the PHP Chinese website!