Maze Path Finding

XXX. Maze Path Finding

Graph

BFS

Problem Statement:

Given a maze represented by a binary 2D array, find if there exists a path from the start position to the destination. The ball can only roll in four directions (up, down, left, right) and will keep rolling until hitting a wall.

• The maze is represented by a binary 2D array where 0 represents empty space and 1 represents a wall.
• The ball must stop at the destination position.
• The ball can pass through the destination but must eventually stop there.

Algorithm:

1. Use a **BFS** approach with modifications:
   • Instead of moving one step, keep rolling in a direction until hitting a wall
   • Track visited positions to avoid cycles
   • Use direction vectors for movement control
2. Process each position:
   • Roll in all four directions from current position
   • Track the last valid position before hitting a wall
   • Add new valid positions to the queue
3. Stop conditions:
   • Found destination position
   • No more positions to explore

Complexity:

Time Complexity: O(m × n), where m and n are the dimensions of the maze.
Space Complexity: O(m × n) for the visited array and queue.

Implementation:

public boolean hasPath(int[][] maze, int[] start, int[] dest) {
    Queue q = new LinkedList<>();
    q.add(new Tuple(start[0], start[1]));
    int m = maze.length, n = maze[0].length;
    boolean[][] visited = new boolean[m][n];
    
    int[] dx = {1, -1, 0, 0};              // Direction vectors for down, up, right, left
    int[] dy = {0, 0, 1, -1};
    
    while (!q.isEmpty()) {
        Tuple curr = q.poll();
        if (curr.x == dest[0] && curr.y == dest[1]) return true;
        
        for (int i = 0; i < dx.length; i++) {
            int newX = curr.x, newY = curr.y;
            // Roll the ball until hitting a wall
            while (newX >= 0 && newY >= 0 && newX < m && newY < n && maze[newX][newY] == 0) {
                newX += dx[i];
                newY += dy[i];
            }
            // Move back one step from the wall
            newX -= dx[i];
            newY -= dy[i];
            
            if (visited[newX][newY]) continue;
            visited[newX][newY] = true;
            q.add(new Tuple(newX, newY));
        }
    }
    return false;
}

class Tuple {
    int x, y;
    public Tuple(int x, int y) {
        this.x = x;
        this.y = y;
    }
}
                

Explanation:

• **Queue Operations**:
  • Use a queue to process positions in BFS order
  • Each queue element contains (x, y) coordinates
• **Direction Handling**:
  • Use dx, dy arrays to represent four possible directions
  • Continue moving in a direction until hitting a wall
  • Track back one step to get the valid position
• **Visited Array**:
  • Prevents revisiting positions
  • Ensures algorithm termination
  • Optimizes exploration by avoiding cycles