BFS — 進階變形

/**
 * Pattern: Multi-Source BFS for Distance Calculation
 * Use case: Calculate shortest distance from each cell to any source cell
 * Key insight: Start BFS from ALL sources simultaneously - first visit guarantees shortest path
 *
 * Time: O(m × n) - each cell visited at most once
 * Space: O(m × n) - queue can hold entire grid in worst case
 */
public int[][] multiSourceBFS(int[][] mat) {
    int rows = mat.length;
    int cols = mat[0].length;
    Queue<int[]> queue = new LinkedList<>();

    // Step 1: Initialize - Add all sources (0s) to queue, mark others as unvisited
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (mat[r][c] == 0) {
                queue.offer(new int[]{r, c});  // Multi-source starting points
            } else {
                // Mark as unvisited - two common approaches:
                // Option A: mat[r][c] = -1 (easier to check)
                // Option B: mat[r][c] = Integer.MAX_VALUE (easier for min comparison)
                mat[r][c] = -1;
            }
        }
    }

    int[][] dirs = {{1,0}, {-1,0}, {0,1}, {0,-1}};

    // Step 2: BFS expansion from all sources
    while (!queue.isEmpty()) {
        int[] cur = queue.poll();
        int r = cur[0], c = cur[1];

        for (int[] d : dirs) {
            int nr = r + d[0];
            int nc = c + d[1];

            // Only process unvisited cells
            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && mat[nr][nc] == -1) {
                // KEY: Distance = parent's distance + 1
                mat[nr][nc] = mat[r][c] + 1;
                queue.offer(new int[]{nr, nc});
            }
        }
    }

    return mat;
}

Problem: Find distance to nearest 0 for each cell
Input:  [[0,0,0],     Output: [[0,0,0],
         [0,1,0],              [0,1,0],
         [1,1,1]]              [1,2,1]]

Execution trace:
Step 1 - Initialize:
  Queue: [(0,0), (0,1), (0,2), (1,0), (1,2)]  ← All 0s
  Grid:  [[0, 0, 0],
          [0, -1, 0],
          [-1, -1, -1]]

Step 2 - BFS Layer 1 (distance = 1):
  Process (0,0): Check (1,0) - already 0, skip
  Process (0,1): Check (1,1) - is -1, update to 1, enqueue
  Process (1,0): Check (2,0) - is -1, update to 1, enqueue

  Grid:  [[0, 0, 0],
          [0, 1, 0],
          [1, -1, -1]]
  Queue: [(1,1), (2,0), ...]

Step 3 - BFS Layer 2 (distance = 2):
  Process (1,1): Check (2,1) - is -1, update to 2, enqueue
  Process (2,0): Check (2,1) - is -1, update to 2, enqueue (redundant)

  Final: [[0, 0, 0],
          [0, 1, 0],
          [1, 2, 1]]

❌ Naive Approach: Start BFS from each target cell
   - For each 1, run BFS to find nearest 0
   - Time: O(m×n) targets × O(m×n) BFS = O(m²×n²) ❌

✅ Multi-Source Approach: Start BFS from ALL sources simultaneously
   - Add all 0s to queue initially
   - Run single BFS that expands from all sources
   - Time: O(m×n) - each cell visited once ✅

/**
 * Pattern: DFS to identify first component, then Multi-Source BFS to find shortest distance to second component
 * Use case: Find shortest bridge between two islands, connect two separate regions
 * Key insight: DFS marks entire first island, BFS expands from ALL cells of first island simultaneously
 *
 * Time: O(m × n) - each cell visited at most once by DFS + once by BFS
 * Space: O(m × n) - queue can hold entire island boundary
 */
public int dfsMarkThenMultiSourceBFS(int[][] grid) {
    int n = grid.length;
    Queue<int[]> queue = new LinkedList<>();
    boolean found = false;

    // Step 1: DFS to find and mark first island (change 1 → 2)
    // Add ALL cells of first island to queue for multi-source BFS
    for (int y = 0; y < n && !found; y++) {
        for (int x = 0; x < n && !found; x++) {
            if (grid[y][x] == 1) {
                dfsMarkIsland(grid, x, y, queue);
                found = true;
            }
        }
    }

    // Step 2: Multi-Source BFS from entire first island
    // Expand outward layer by layer until reaching second island
    int[][] dirs = {{1,0}, {-1,0}, {0,1}, {0,-1}};
    int steps = 0;
    boolean[][] visited = new boolean[n][n];

    while (!queue.isEmpty()) {
        int size = queue.size();

        for (int i = 0; i < size; i++) {
            int[] cur = queue.poll();
            int x = cur[0], y = cur[1];

            for (int[] d : dirs) {
                int nx = x + d[0];
                int ny = y + d[1];

                if (nx >= 0 && nx < n && ny >= 0 && ny < n && !visited[ny][nx]) {
                    visited[ny][nx] = true;

                    if (grid[ny][nx] == 1) {
                        return steps; // Reached second island
                    }

                    if (grid[ny][nx] == 0) {
                        queue.add(new int[]{nx, ny});
                    }
                }
            }
        }
        steps++;
    }

    return -1;
}

// DFS helper: Mark all cells of first island and add to queue
void dfsMarkIsland(int[][] grid, int x, int y, Queue<int[]> queue) {
    int n = grid.length;
    if (x < 0 || x >= n || y < 0 || y >= n || grid[y][x] != 1) {
        return;
    }

    grid[y][x] = 2; // Mark as visited (part of first island)
    queue.add(new int[]{x, y}); // Add to BFS queue

    // Recursively mark all connected cells
    dfsMarkIsland(grid, x + 1, y, queue);
    dfsMarkIsland(grid, x - 1, y, queue);
    dfsMarkIsland(grid, x, y + 1, queue);
    dfsMarkIsland(grid, x, y - 1, queue);
}

Problem: Connect two islands with minimum number of flips (0→1)
Grid: [[0,1],     Two islands: Island A at (0,1), Island B at (1,0)
       [1,0]]     Need to flip 1 cell to connect them

Step 1 - DFS marks Island A:
Original: [0,1]  →  After DFS: [0,2]  (2 = marked as first island)
          [1,0]                [1,0]
Queue: [(1,0)] - all cells of first island

Step 2 - BFS Layer 0 (from first island):
Check neighbors of (1,0):
- (0,0): water, add to queue → Queue: [(0,0)]
- (1,1): water, add to queue → Queue: [(0,0), (1,1)]
After Layer 0: steps = 0

Step 3 - BFS Layer 1:
Process (0,0):
  - (1,0): already visited (marked as 2)
  - (0,1): FOUND Island B (value = 1)! Return steps = 0

Result: 1 flip needed (but we count layers, answer may vary based on problem definition)

Key insight:
- DFS ensures we mark ENTIRE first island (not just one cell)
- Multi-source BFS expands from ALL boundary cells simultaneously
- This guarantees we find the absolute shortest bridge

// Simultaneous Multi-Source BFS Template
public int[][] simultaneousMultiSourceBFS(int[][] grid) {
    Queue<int[]> queue = new LinkedList<>();
    boolean[][] visited = new boolean[rows][cols];

    // Add ALL sources to queue at once
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (grid[r][c] == SOURCE) {
                queue.offer(new int[]{r, c});
                visited[r][c] = true;  // ONE shared visited array
            }
        }
    }

    // Single BFS run - all sources expand together
    while (!queue.isEmpty()) {
        int[] cur = queue.poll();
        // Process neighbors...
        // First visit to any cell = shortest distance from ANY source
    }
}

// Independent BFS Runs Template - LC 317 Pattern
public int independentBFSRuns(int[][] grid) {
    int rows = grid.length;
    int cols = grid[0].length;

    // Global accumulator - each BFS adds to this
    int[][] totalDist = new int[rows][cols];
    int[][] reachCount = new int[rows][cols];

    int buildingCount = 0;

    // Run SEPARATE BFS for each source
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (grid[r][c] == 1) {  // Found a building (source)
                buildingCount++;

                // FRESH visited array for this building's BFS
                boolean[][] visited = new boolean[rows][cols];

                bfsSingleSource(grid, r, c, visited, totalDist, reachCount);
            }
        }
    }

    // Find best cell that was reached by ALL buildings
    int minDist = Integer.MAX_VALUE;
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (grid[r][c] == 0 && reachCount[r][c] == buildingCount) {
                minDist = Math.min(minDist, totalDist[r][c]);
            }
        }
    }

    return minDist == Integer.MAX_VALUE ? -1 : minDist;
}

// BFS from single source - accumulates distances
private void bfsSingleSource(int[][] grid, int sr, int sc,
                             boolean[][] visited,
                             int[][] totalDist,
                             int[][] reachCount) {
    Queue<int[]> queue = new LinkedList<>();
    queue.offer(new int[]{sr, sc});
    visited[sr][sc] = true;

    int[][] dirs = {{0,1}, {0,-1}, {1,0}, {-1,0}};
    int dist = 0;

    while (!queue.isEmpty()) {
        int size = queue.size();
        dist++;

        for (int i = 0; i < size; i++) {
            int[] cur = queue.poll();
            int r = cur[0], c = cur[1];

            for (int[] d : dirs) {
                int nr = r + d[0];
                int nc = c + d[1];

                if (nr >= 0 && nr < grid.length && nc >= 0 && nc < grid[0].length
                    && !visited[nr][nc] && grid[nr][nc] == 0) {

                    visited[nr][nc] = true;

                    // Accumulate distance from this building
                    totalDist[nr][nc] += dist;
                    reachCount[nr][nc]++;

                    queue.offer(new int[]{nr, nc});
                }
            }
        }
    }
}

Building A runs BFS:
  - Visits land cell (2,3) and marks it visited ✓
  - Calculates: distance from A to (2,3) = 5 steps

Building B runs BFS:
  - If we reuse visited array, cell (2,3) is still marked as visited!
  - We would SKIP (2,3) and never calculate distance from B to (2,3) ❌

But we NEED both distances because:
  - totalDist[2][3] = distFromA + distFromB + distFromC + ...

// ❌ WRONG - Reusing visited array
boolean[][] visited = new boolean[rows][cols];  // Created ONCE

for (Building b : allBuildings) {
    bfs(b, visited);  // All buildings share same visited array
    // Later buildings can't visit cells that earlier buildings marked!
}

// ✅ CORRECT - Fresh visited array
for (Building b : allBuildings) {
    boolean[][] visited = new boolean[rows][cols];  // Fresh each time
    bfs(b, visited);  // Each building can visit all reachable cells
}

// LC 317 Optimization: Decrement empty cells for each building
public int shortestDistance(int[][] grid) {
    int[][] totalDist = new int[rows][cols];
    int emptyValue = 0;  // Changes with each BFS: 0 → -1 → -2 → -3...
    int buildingCount = 0;

    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (grid[r][c] == 1) {
                buildingCount++;

                // BFS from this building, only visit cells with value = emptyValue
                bfsWithGridMarking(grid, r, c, emptyValue, totalDist);

                emptyValue--;  // Next building looks for different value
            }
        }
    }

    // Find best cell with value = (emptyValue + 1)
    // That cell was reached by ALL buildings
}

private void bfsWithGridMarking(int[][] grid, int sr, int sc,
                               int targetValue, int[][] totalDist) {
    // Only process cells with grid[r][c] == targetValue
    // After processing, change to (targetValue - 1)
    // This ensures cell must be reached by ALL previous buildings
}

Initial grid: All empty cells = 0

Building 1 BFS:
  - Visit cells with value 0
  - Change them to -1 after visiting
  - Now empty cells = -1

Building 2 BFS:
  - Only visit cells with value -1
  - Change them to -2 after visiting
  - Now only cells reachable by BOTH buildings = -2

Building 3 BFS:
  - Only visit cells with value -2
  - Change them to -3
  - Only cells reachable by ALL 3 buildings = -3

Problem: Transform "hit" → "cog" using dictionary ["hot","dot","dog","lot","log","cog"]
Expected: 5 (hit → hot → dot → dog → cog)

BFS + Backtracking Execution:

Layer 0: Queue = [hit], steps = 1
  Process "hit":
    Position 0: h→a,b,c,...,z  (none in dict)
    Position 1: i→a,b,c,...,o,... → "hot" ✓ add to queue
    Position 2: t→a,b,c,...,g,... (none in dict besides "hit" itself)
  After Layer 0: Queue = [hot]

Layer 1: Queue = [hot], steps = 2
  Process "hot":
    Position 0: h→a,b,c,...,d → "dot" ✓, "lot" ✓
    Position 1: o→... (backtrack, restore 'o')
    Position 2: t→... (none found)
  After Layer 1: Queue = [dot, lot]

Layer 2: Queue = [dot, lot], steps = 3
  Process "dot":
    Position 0: d→... (none found)
    Position 1: o→... (none found)
    Position 2: t→g → "dog" ✓
  Process "lot":
    Position 0: l→... (none found)
    Position 1: o→... (none found)
    Position 2: t→g → "log" ✓
  After Layer 2: Queue = [dog, log]

Layer 3: Queue = [dog, log], steps = 4
  Process "dog":
    Position 0: d→... (none found)
    Position 1: o→... (none found)
    Position 2: g→... (none found)
  Process "log":
    Position 0: l→... (none found)
    Position 1: o→... (none found)
    Position 2: g→c → "cog" ✓
  After Layer 3: Queue = [cog]

Layer 4: Queue = [cog], steps = 5
  Process "cog":
    cur.equals(endWord) == true
  RETURN steps = 5 ✓

❌ Naive Approach (without backtracking):
   For each position, generate ONE new word per letter
   Problem: Must process all positions with CORRECT base state

✅ Backtracking Approach:
   1. Modify position 0 → try all 26 letters
   2. Restore position 0 to original
   3. Modify position 1 → try all 26 letters (with position 0 restored!)
   4. Restore position 1 to original
   5. Continue to position 2, etc.

   Result: Each position explored independently with correct base state

/**
 * Pattern: BFS where nodes are ROUTES (buses/lines), not physical locations
 * Use case: Find minimum number of transfers/buses to reach a destination
 * Key insight: Build stop→routes mapping, BFS on routes with two visited sets (buses + stops)
 *
 * Time: O(N * M) where N = number of routes, M = avg stops per route
 * Space: O(N * M) for the stop-to-routes map and visited sets
 */
public int routeLevelBFS(int[][] routes, int source, int target) {
    if (source == target) return 0;

    // Step 1: Build mapping from stop → list of route IDs
    Map<Integer, List<Integer>> stopToRoutes = new HashMap<>();
    for (int i = 0; i < routes.length; i++) {
        for (int stop : routes[i]) {
            stopToRoutes.computeIfAbsent(stop, k -> new ArrayList<>()).add(i);
        }
    }

    // Step 2: BFS on route IDs (not stops!)
    Queue<Integer> queue = new LinkedList<>();
    Set<Integer> visitedRoutes = new HashSet<>();
    Set<Integer> visitedStops = new HashSet<>();

    // Seed: all routes that pass through the source stop
    for (int routeId : stopToRoutes.getOrDefault(source, new ArrayList<>())) {
        queue.offer(routeId);
        visitedRoutes.add(routeId);
    }

    int busCount = 1; // Already on the first bus

    while (!queue.isEmpty()) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            int currRoute = queue.poll();

            // Check all stops on this route
            for (int stop : routes[currRoute]) {
                if (stop == target) return busCount;

                if (visitedStops.contains(stop)) continue;
                visitedStops.add(stop);

                // Transfer: enqueue all OTHER routes at this stop
                for (int nextRoute : stopToRoutes.getOrDefault(stop, new ArrayList<>())) {
                    if (!visitedRoutes.contains(nextRoute)) {
                        visitedRoutes.add(nextRoute);
                        queue.offer(nextRoute);
                    }
                }
            }
        }
        busCount++;
    }

    return -1;
}

Problem: Find minimum buses to travel from source=1 to target=6
Routes: [[1,2,7], [3,6,7]]
  Route 0: stops 1→2→7→1→...
  Route 1: stops 3→6→7→3→...

Step 1 - Build stop→routes map:
  1 → [Route 0]
  2 → [Route 0]
  7 → [Route 0, Route 1]   ← transfer point!
  3 → [Route 1]
  6 → [Route 1]

Step 2 - BFS:
  Source stop = 1 → seed Route 0 into queue
  Queue: [Route 0], busCount = 1

  Layer 1 (busCount = 1):
    Process Route 0 → check stops [1, 2, 7]:
      Stop 1: not target. Routes at stop 1 = [Route 0] (already visited)
      Stop 2: not target. Routes at stop 2 = [Route 0] (already visited)
      Stop 7: not target. Routes at stop 7 = [Route 0, Route 1]
        → Route 1 not visited → enqueue Route 1
    Queue: [Route 1]

  busCount++ → busCount = 2

  Layer 2 (busCount = 2):
    Process Route 1 → check stops [3, 6, 7]:
      Stop 3: not target
      Stop 6: == target! → return busCount = 2 ✓

visitedRoutes: Prevents boarding the same bus twice (infinite loop)
visitedStops:  Prevents re-processing transfer points
               (stop 7 connects Routes 0 and 1, but once explored, no need to revisit)

Without visitedStops: Every stop would re-check all its routes
  → Redundant work, potentially O(N²*M) instead of O(N*M)

❌ BFS on stops: Queue = [stop1, stop2, ...]
   Problem: How do you define "neighbors" of a stop?
   All other stops on the SAME route → huge adjacency list
   Loses the concept of "how many buses taken"

✅ BFS on routes: Queue = [route0, route1, ...]
   Each BFS layer = one bus ride
   Transfer = finding a new route at a shared stop
   busCount directly maps to BFS depth

/**
 * Pattern: BFS to build shortest-path DAG, then DFS to enumerate all paths
 * Use case: Find ALL shortest transformation sequences (not just one)
 * Key insight: BFS builds a reverse graph of predecessors, DFS reconstructs all valid paths
 *
 * Time: O(N * M * 26 + paths) where N=words, M=length, paths=output size
 * Space: O(N * M) for graph + O(M) for DFS recursion stack
 */
public List<List<String>> findAllShortestPaths(String beginWord, String endWord, List<String> wordList) {
    List<List<String>> result = new ArrayList<>();
    Set<String> wordSet = new HashSet<>(wordList);

    if (!wordSet.contains(endWord))
        return result;

    // Map to store: word → list of predecessors (parents) at shortest distance
    Map<String, List<String>> parents = new HashMap<>();

    // Map to store: word → shortest distance from beginWord
    Map<String, Integer> distances = new HashMap<>();

    // ========== PHASE 1: BFS to build shortest-path DAG ==========
    Queue<String> queue = new LinkedList<>();
    queue.add(beginWord);
    distances.put(beginWord, 0);

    boolean found = false;
    String alpha = "abcdefghijklmnopqrstuvwxyz";

    while (!queue.isEmpty() && !found) {
        int size = queue.size();

        /**
         * CRITICAL: Use levelVisited to allow multiple parents at same distance
         *
         * Why separate from main visited set?
         * - Allows a word to be reached from multiple neighbors in same level
         * - We record ALL parents that reach it in shortest distance
         * - Main visited updated AFTER processing entire level
         *
         * Without this, we'd lose valid shortest paths!
         */
        Set<String> levelVisited = new HashSet<>();

        for (int i = 0; i < size; i++) {
            String word = queue.poll();
            char[] chars = word.toCharArray();

            for (int j = 0; j < chars.length; j++) {
                char original = chars[j];

                for (char c : alpha.toCharArray()) {
                    if (c == original)
                        continue;

                    chars[j] = c;
                    String nextWord = new String(chars);

                    // Skip words not in dictionary
                    if (!wordSet.contains(nextWord))
                        continue;

                    int newDistance = distances.get(word) + 1;

                    /**
                     * KEY LOGIC: Record ALL predecessors at shortest distance
                     *
                     * Case 1: First time reaching nextWord
                     * - Set distance
                     * - Add current word as first predecessor
                     * - Enqueue for next level
                     *
                     * Case 2: Reaching nextWord again at SAME distance (same level)
                     * - Add current word as ANOTHER predecessor
                     * - Don't enqueue again (already enqueued in this level)
                     *
                     * Case 3: Reaching nextWord at LONGER distance
                     * - Ignore (we only want shortest paths)
                     */
                    if (!distances.containsKey(nextWord)) {
                        // Case 1: First time reaching this word
                        distances.put(nextWord, newDistance);
                        parents.computeIfAbsent(nextWord, k -> new ArrayList<>()).add(word);

                        if (!levelVisited.contains(nextWord)) {
                            levelVisited.add(nextWord);
                            queue.add(nextWord);
                        }

                        if (nextWord.equals(endWord)) {
                            found = true;
                        }
                    } else if (distances.get(nextWord) == newDistance) {
                        // Case 2: Same distance from another parent
                        parents.computeIfAbsent(nextWord, k -> new ArrayList<>()).add(word);
                    }
                    // Case 3: Longer distance - ignore
                }

                chars[j] = original;  // Restore after exploring all letters
            }
        }
    }

    // ========== PHASE 2: DFS to enumerate all paths ==========
    if (distances.containsKey(endWord)) {
        List<String> path = new LinkedList<>();
        dfsEnumeratePaths(endWord, beginWord, parents, path, result);
    }

    return result;
}

/**
 * DFS backtracking to reconstruct all paths from endWord to beginWord
 *
 * Why backward (from endWord to beginWord)?
 * - parents map stores: word → predecessors
 * - Easier to traverse backward from target to source
 * - Build path in reverse, then it's already correct order when we reach beginWord
 */
private void dfsEnumeratePaths(String current, String beginWord,
                               Map<String, List<String>> parents,
                               List<String> path, List<List<String>> result) {
    // Add current word to path (building backward)
    path.add(0, current);

    // Base case: reached the beginning
    if (current.equals(beginWord)) {
        result.add(new ArrayList<>(path));
    } else {
        // Recursive case: explore all predecessors
        List<String> predecessors = parents.get(current);
        if (predecessors != null) {
            for (String prev : predecessors) {
                dfsEnumeratePaths(prev, beginWord, parents, path, result);
            }
        }
    }

    // Backtrack: remove current word before returning
    path.remove(0);
}

Problem: Find ALL shortest paths from "hit" to "cog"
Dictionary: ["hot","dot","dog","lot","log","cog"]
Expected: [["hit","hot","dot","dog","cog"], ["hit","hot","lot","log","cog"]]

========== BFS PHASE ==========

Level 0: Queue = [hit], distances = {hit:0}
  Process "hit":
    Neighbors: "hot" (only one in dict differing by 1 letter)
    distances[hot] = 1, parents[hot] = [hit]
    levelVisited = {hot}
  After level: visited = {hit, hot}

Level 1: Queue = [hot], distances = {hit:0, hot:1}
  Process "hot":
    Neighbors: "dot", "lot", "hit" (hit already visited at distance 0, skip)
    distances[dot] = 2, parents[dot] = [hot]
    distances[lot] = 2, parents[lot] = [hot]
    levelVisited = {dot, lot}
  After level: visited = {hit, hot, dot, lot}

Level 2: Queue = [dot, lot], distances = {hit:0, hot:1, dot:2, lot:2}
  Process "dot":
    Neighbors: "dog", "hot" (hot at distance 1, skip)
    distances[dog] = 3, parents[dog] = [dot]
  Process "lot":
    Neighbors: "log", "hot" (hot at distance 1, skip)
    distances[log] = 3, parents[log] = [lot]
    levelVisited = {dog, log}
  After level: visited = {hit, hot, dot, lot, dog, log}

Level 3: Queue = [dog, log], distances = {hit:0, hot:1, dot:2, lot:2, dog:3, log:3}
  Process "dog":
    Neighbors: "cog", "dot" (dot at distance 2, skip)
    distances[cog] = 4, parents[cog] = [dog]
    found = true
  Process "log":
    Neighbors: "cog", "lot" (lot at distance 2, skip)
    cog already has distance 4, same as current+1!
    parents[cog] = [dog, log]  ← KEY: multiple parents!
  After level: visited = {hit, hot, dot, lot, dog, log, cog}

STOP BFS (found = true after finishing level)

Final parents map:
  cog → [dog, log]
  dog → [dot]
  log → [lot]
  dot → [hot]
  lot → [hot]
  hot → [hit]

========== DFS PHASE ==========

DFS from "cog" to "hit":

dfs(cog):
  path = [cog]
  predecessors = [dog, log]

  dfs(dog):
    path = [dog, cog]
    predecessors = [dot]

    dfs(dot):
      path = [dot, dog, cog]
      predecessors = [hot]

      dfs(hot):
        path = [hot, dot, dog, cog]
        predecessors = [hit]

        dfs(hit):
          path = [hit, hot, dot, dog, cog]
          hit == beginWord → FOUND PATH!
          result = [[hit, hot, dot, dog, cog]]

  dfs(log):
    path = [log, cog]
    predecessors = [lot]

    dfs(lot):
      path = [lot, log, cog]
      predecessors = [hot]

      dfs(hot):
        path = [hot, lot, log, cog]
        predecessors = [hit]

        dfs(hit):
          path = [hit, hot, lot, log, cog]
          hit == beginWord → FOUND PATH!
          result = [[hit, hot, dot, dog, cog], [hit, hot, lot, log, cog]]

Final result: 2 paths found ✓

Input: s = "{a,b}c{d,e}f"
Parsed groups: [["a","b"], ["c"], ["d","e"], ["f"]]

Start:
  queue = [""]

After group ["a","b"]  (level 1):
  Drain "" → append "a", "b"
  queue = ["a", "b"]

After group ["c"]      (level 2):
  Drain "a" → "ac"
  Drain "b" → "bc"
  queue = ["ac", "bc"]

After group ["d","e"]  (level 3):
  Drain "ac" → "acd", "ace"
  Drain "bc" → "bcd", "bce"
  queue = ["acd", "ace", "bcd", "bce"]

After group ["f"]      (level 4):
  queue = ["acdf", "acef", "bcdf", "bcef"]   ← final result

// Pattern 9: BFS-Style Cartesian Product Generation
// Time: O(G * |result|) where G = number of groups, |result| = total combinations
// Space: O(|result|) for the queue at the final level
public String[] cartesianBFS(List<List<String>> groups) {
    Queue<String> queue = new LinkedList<>();
    queue.add("");  // seed: one empty prefix at depth 0

    for (List<String> group : groups) {
        int size = queue.size();  // snapshot current layer size
        for (int k = 0; k < size; k++) {
            String prefix = queue.poll();
            for (String option : group) {
                queue.add(prefix + option);  // expand: prefix × option
            }
        }
        // After the loop: queue holds exactly one layer deeper
    }

    String[] res = new String[queue.size()];
    int idx = 0;
    while (!queue.isEmpty()) res[idx++] = queue.poll();
    return res;
}

// Use State(prefix, groupIndex) so the BFS loop drives termination
Queue<State> queue = new LinkedList<>();
queue.add(new State("", 0));

while (!queue.isEmpty()) {
    State cur = queue.poll();
    if (cur.groupIndex == groups.size()) {
        result.add(cur.prefix);  // leaf: complete combination
        continue;
    }
    for (String opt : groups.get(cur.groupIndex))
        queue.add(new State(cur.prefix + opt, cur.groupIndex + 1));
}

// java
// LC 301 - Remove Invalid Parentheses
// time = O(2^n * n)  worst case every subset of chars; n per validity check
// space = O(2^n)     visited set + queue
// IDEA: 1 BFS level = 1 deletion. First level containing a valid string is the answer level.
public List<String> removeInvalidParentheses(String s) {
    List<String> res = new ArrayList<>();
    Set<String> visited = new HashSet<>();
    Queue<String> q = new LinkedList<>();
    q.offer(s);
    visited.add(s);
    boolean found = false;
    while (!q.isEmpty()) {
        int size = q.size();
        for (int i = 0; i < size; i++) {
            String cur = q.poll();
            if (isValid(cur)) { res.add(cur); found = true; }
            if (found) continue;               // drain this level, but stop expanding
            for (int j = 0; j < cur.length(); j++) {
                char c = cur.charAt(j);
                if (c != '(' && c != ')') continue;   // only parens are removable
                String next = cur.substring(0, j) + cur.substring(j + 1);
                if (visited.add(next)) q.offer(next); // add() returns false if dup
            }
        }
        if (found) return res;                 // this level is minimal -> done
    }
    return res;
}

private boolean isValid(String t) {
    int cnt = 0;
    for (char c : t.toCharArray()) {
        if (c == '(') cnt++;
        else if (c == ')' && --cnt < 0) return false;  // ')' before its '('
    }
    return cnt == 0;
}

# python
# LC 301 - Remove Invalid Parentheses
# time = O(2^n * n), space = O(2^n)
# IDEA: level = number of deletions; return the first level that has valid strings
def removeInvalidParentheses(s):
    def valid(t):
        cnt = 0
        for ch in t:
            if ch == '(':
                cnt += 1
            elif ch == ')':
                cnt -= 1
                if cnt < 0:
                    return False
        return cnt == 0

    level = {s}                       # a set IS the visited-dedup for this level
    while level:
        found = [t for t in level if valid(t)]
        if found:
            return found              # minimal deletions -> all answers of this size
        nxt = set()
        for t in level:
            for i, ch in enumerate(t):
                if ch in '()':        # letters are never removed
                    nxt.add(t[:i] + t[i + 1:])
        level = nxt
    return [""]

visited on (r, c)              ->  visited on (r, c, resource)

// java
// LC 864 - Shortest Path to Get All Keys
// IDEA: BFS over (row, col, keyMask). A lock is passable only when its bit is already
//       in the mask; stepping on a key ORs its bit in. Answer = first pop with all keys.
// time = O(m*n*2^k), space = O(m*n*2^k)
public int shortestPathAllKeys(String[] grid) {
    int m = grid.length, n = grid[0].length();
    int startR = 0, startC = 0, allKeys = 0;
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            char ch = grid[r].charAt(c);
            if (ch == '@') { startR = r; startC = c; }
            else if (ch >= 'a' && ch <= 'f') allKeys |= 1 << (ch - 'a');
        }
    }

    int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
    boolean[][][] seen = new boolean[m][n][1 << 6];   // NOTE !!! the mask is part of the key
    Queue<int[]> q = new LinkedList<>();
    q.offer(new int[]{startR, startC, 0});
    seen[startR][startC][0] = true;

    int steps = 0;
    while (!q.isEmpty()) {
        int size = q.size();
        for (int s = 0; s < size; s++) {
            int[] cur = q.poll();
            int r = cur[0], c = cur[1], mask = cur[2];
            if (mask == allKeys) return steps;

            for (int[] d : dirs) {
                int nr = r + d[0], nc = c + d[1];
                if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
                char ch = grid[nr].charAt(nc);
                if (ch == '#') continue;
                // a lock we have no key for is a wall
                if (ch >= 'A' && ch <= 'F' && (mask & (1 << (ch - 'A'))) == 0) continue;

                int nMask = mask;
                if (ch >= 'a' && ch <= 'f') nMask |= 1 << (ch - 'a');
                if (seen[nr][nc][nMask]) continue;
                seen[nr][nc][nMask] = true;
                q.offer(new int[]{nr, nc, nMask});
            }
        }
        steps++;
    }
    return -1;
}

# python
# LC 864 - Shortest Path to Get All Keys
# IDEA: same BFS, state = (r, c, keyMask); picking up a key moves you to a DIFFERENT
#       layer of the search space, which is why a cell can be visited up to 2^k times
# time = O(m*n*2^k), space = O(m*n*2^k)
from collections import deque

def shortestPathAllKeys(grid):
    m, n = len(grid), len(grid[0])
    all_keys = 0
    start = (0, 0)
    for r in range(m):
        for c in range(n):
            ch = grid[r][c]
            if ch == '@':
                start = (r, c)
            elif ch.islower():
                all_keys |= 1 << (ord(ch) - ord('a'))

    q = deque([(start[0], start[1], 0, 0)])       # r, c, mask, steps
    seen = {(start[0], start[1], 0)}
    while q:
        r, c, mask, steps = q.popleft()
        if mask == all_keys:
            return steps
        for dr, dc in ((0, 1), (0, -1), (1, 0), (-1, 0)):
            nr, nc = r + dr, c + dc
            if not (0 <= nr < m and 0 <= nc < n):
                continue
            ch = grid[nr][nc]
            if ch == '#':
                continue
            if ch.isupper() and not (mask >> (ord(ch) - ord('A'))) & 1:
                continue                          # locked door, no key -> a wall
            n_mask = mask | (1 << (ord(ch) - ord('a'))) if ch.islower() else mask
            if (nr, nc, n_mask) in seen:
                continue
            seen.add((nr, nc, n_mask))
            q.append((nr, nc, n_mask, steps + 1))
    return -1

// java
// LC 1293 - Shortest Path in a Grid with Obstacles Elimination
// IDEA: BFS over (row, col, k left). best[r][c] = most budget ever seen here; an arrival
//       with <= that budget can never do better, so drop it.
// time = O(m*n*k), space = O(m*n)
public int shortestPath(int[][] grid, int k) {
    int m = grid.length, n = grid[0].length;
    if (k >= m + n - 2) return m + n - 2;        // enough budget to walk the diagonal

    int[][] best = new int[m][n];
    for (int[] row : best) Arrays.fill(row, -1);
    int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};

    Queue<int[]> q = new LinkedList<>();
    q.offer(new int[]{0, 0, k});
    best[0][0] = k;

    int steps = 0;
    while (!q.isEmpty()) {
        int size = q.size();
        for (int s = 0; s < size; s++) {
            int[] cur = q.poll();
            int r = cur[0], c = cur[1], left = cur[2];
            if (r == m - 1 && c == n - 1) return steps;

            for (int[] d : dirs) {
                int nr = r + d[0], nc = c + d[1];
                if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
                int nLeft = left - grid[nr][nc];   // grid is 0/1, so this spends the budget
                /** NOTE !!! `<=` not `<` — an arrival with the same budget is a duplicate,
                 *  and it is arriving no earlier, so it can never win. */
                if (nLeft < 0 || nLeft <= best[nr][nc]) continue;
                best[nr][nc] = nLeft;
                q.offer(new int[]{nr, nc, nLeft});
            }
        }
        steps++;
    }
    return -1;
}

# python
# LC 1293 - Shortest Path in a Grid with Obstacles Elimination
# IDEA: BFS over (r, c, k remaining); prune with the best budget ever seen at a cell
# time = O(m*n*k), space = O(m*n)
from collections import deque

def shortestPath(grid, k):
    m, n = len(grid), len(grid[0])
    if k >= m + n - 2:
        return m + n - 2

    best = [[-1] * n for _ in range(m)]
    best[0][0] = k
    q = deque([(0, 0, k, 0)])                     # r, c, k left, steps
    while q:
        r, c, left, steps = q.popleft()
        if (r, c) == (m - 1, n - 1):
            return steps
        for dr, dc in ((0, 1), (0, -1), (1, 0), (-1, 0)):
            nr, nc = r + dr, c + dc
            if not (0 <= nr < m and 0 <= nc < n):
                continue
            n_left = left - grid[nr][nc]
            if n_left < 0 or n_left <= best[nr][nc]:
                continue                          # out of budget, or already been here richer
            best[nr][nc] = n_left
            q.append((nr, nc, n_left, steps + 1))
    return -1

# python — Tree → Graph conversion + per-leaf bounded BFS (LC 1530)
# time  = O(L * (V + E)) = O(L * N)   L = #leaves, N = #nodes
# space = O(N)                        adjacency map + queue/visited
from collections import deque, defaultdict

class Solution:
    def countPairs(self, root, distance):
        leaves = []
        graph = defaultdict(list)

        # Step 1: collect leaves + build UNDIRECTED graph
        def build(node, parent=None):
            if not node:
                return
            if not node.left and not node.right:   # leaf
                leaves.append(node)
            if parent:                              # bidirectional edge
                graph[node].append(parent)
                graph[parent].append(node)
            build(node.left, node)
            build(node.right, node)
        build(root)

        cnt = 0
        # Step 2: bounded BFS from every leaf
        for leaf in leaves:
            queue = deque([(leaf, 0)])              # (node, dist)
            visited = {leaf}
            while queue:
                cur, d = queue.popleft()
                if cur != leaf and not cur.left and not cur.right:
                    cnt += 1                         # reached another leaf
                if d < distance:                     # only expand within limit
                    for nxt in graph[cur]:
                        if nxt not in visited:
                            visited.add(nxt)
                            queue.append((nxt, d + 1))
        return cnt // 2                              # each pair counted twice

// java
// LC 399 - Evaluate Division
// time = O(Q * (V + E)), space = O(V + E)     Q = #queries
// IDEA: weighted graph a->b = v, b->a = 1/v; BFS carries the running product
public double[] calcEquation(List<List<String>> equations, double[] values,
                             List<List<String>> queries) {
    Map<String, Map<String, Double>> g = new HashMap<>();
    for (int i = 0; i < values.length; i++) {
        String a = equations.get(i).get(0), b = equations.get(i).get(1);
        g.computeIfAbsent(a, k -> new HashMap<>()).put(b, values[i]);
        g.computeIfAbsent(b, k -> new HashMap<>()).put(a, 1.0 / values[i]);
    }
    double[] res = new double[queries.size()];
    for (int i = 0; i < queries.size(); i++)
        res[i] = bfs(g, queries.get(i).get(0), queries.get(i).get(1));
    return res;
}

private double bfs(Map<String, Map<String, Double>> g, String src, String dst) {
    if (!g.containsKey(src) || !g.containsKey(dst)) return -1.0;  // unknown variable
    if (src.equals(dst)) return 1.0;
    Queue<Object[]> q = new LinkedList<>();
    Set<String> seen = new HashSet<>();
    q.offer(new Object[]{src, 1.0});
    seen.add(src);
    while (!q.isEmpty()) {
        Object[] cur = q.poll();
        String node = (String) cur[0];
        double prod = (double) cur[1];
        for (Map.Entry<String, Double> e : g.get(node).entrySet()) {
            if (e.getKey().equals(dst)) return prod * e.getValue();
            if (seen.add(e.getKey()))
                q.offer(new Object[]{e.getKey(), prod * e.getValue()});
        }
    }
    return -1.0;   // known variables, but no path connects them
}

# python
# LC 399 - Evaluate Division
# time = O(Q * (V + E)), space = O(V + E)
# IDEA: queue holds (node, product_so_far) instead of (node, distance)
from collections import deque, defaultdict

def calcEquation(equations, values, queries):
    g = defaultdict(dict)
    for (a, b), v in zip(equations, values):
        g[a][b] = v
        g[b][a] = 1.0 / v

    def bfs(src, dst):
        if src not in g or dst not in g:
            return -1.0                     # variable never appeared
        if src == dst:
            return 1.0
        q = deque([(src, 1.0)])
        seen = {src}
        while q:
            node, prod = q.popleft()
            for nxt, w in g[node].items():
                if nxt == dst:
                    return prod * w
                if nxt not in seen:
                    seen.add(nxt)
                    q.append((nxt, prod * w))
        return -1.0

    return [bfs(a, b) for a, b in queries]

// java
// LC 1368 - Minimum Cost to Make at Least One Valid Path in a Grid
// time = O(m*n), space = O(m*n)
// IDEA: 0-1 BFS. Following grid[r][c]'s arrow costs 0 -> push FRONT; turning costs 1 -> push BACK.
public int minCost(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};    // index k <-> grid value k+1
    int[][] dist = new int[m][n];
    for (int[] row : dist) Arrays.fill(row, Integer.MAX_VALUE);
    dist[0][0] = 0;
    Deque<int[]> dq = new ArrayDeque<>();
    dq.offerFirst(new int[]{0, 0});
    while (!dq.isEmpty()) {
        int[] cur = dq.pollFirst();
        int r = cur[0], c = cur[1];
        for (int k = 0; k < 4; k++) {
            int nr = r + dirs[k][0], nc = c + dirs[k][1];
            if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
            int cost = (grid[r][c] == k + 1) ? 0 : 1;
            if (dist[r][c] + cost < dist[nr][nc]) {
                dist[nr][nc] = dist[r][c] + cost;
                if (cost == 0) dq.offerFirst(new int[]{nr, nc});   // 0-weight: front
                else           dq.offerLast(new int[]{nr, nc});    // 1-weight: back
            }
        }
    }
    return dist[m - 1][n - 1];
}

# python
# LC 1368 - Minimum Cost to Make at Least One Valid Path in a Grid
# time = O(m*n), space = O(m*n)
# IDEA: deque BFS - appendleft for 0-cost moves, append for 1-cost moves
def minCost(grid):
    m, n = len(grid), len(grid[0])
    dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]      # grid value 1,2,3,4
    INF = float('inf')
    dist = [[INF] * n for _ in range(m)]
    dist[0][0] = 0
    dq = deque([(0, 0)])
    while dq:
        r, c = dq.popleft()
        for k, (dr, dc) in enumerate(dirs):
            nr, nc = r + dr, c + dc
            if not (0 <= nr < m and 0 <= nc < n):
                continue
            cost = 0 if grid[r][c] == k + 1 else 1
            if dist[r][c] + cost < dist[nr][nc]:
                dist[nr][nc] = dist[r][c] + cost
                if cost == 0:
                    dq.appendleft((nr, nc))        # free move -> front
                else:
                    dq.append((nr, nc))            # paid move -> back
    return dist[m - 1][n - 1]

def bidirectional_bfs(start, end):
    """Meet in the middle - faster for long paths"""
    if start == end:
        return 0
    
    forward = {start: 0}
    backward = {end: 0}
    queue_forward = deque([start])
    queue_backward = deque([end])
    
    while queue_forward or queue_backward:
        # Expand smaller frontier
        if len(forward) <= len(backward):
            if expand_level(queue_forward, forward, backward):
                return True
        else:
            if expand_level(queue_backward, backward, forward):
                return True
    
    return False

import heapq

def weighted_bfs(start, end, graph):
    """BFS variant for weighted graphs"""
    heap = [(0, start)]
    distances = {start: 0}
    
    while heap:
        dist, node = heapq.heappop(heap)
        
        if node == end:
            return dist
            
        if dist > distances.get(node, float('inf')):
            continue
            
        for neighbor, weight in graph[node]:
            new_dist = dist + weight
            if new_dist < distances.get(neighbor, float('inf')):
                distances[neighbor] = new_dist
                heapq.heappush(heap, (new_dist, neighbor))
    
    return -1

/**
 * Pattern: Sort targets by priority, then repeatedly call BFS to find shortest paths
 * Use case: Visit multiple targets in specific order, minimize total travel distance
 * Key insight: BFS guarantees shortest path between each pair of consecutive targets
 *
 * Time: O(k × m × n) where k = number of targets, m×n = grid size
 * Space: O(m × n) for visited array in each BFS call
 */
public int sortAndBFS(List<List<Integer>> grid) {
    int rows = grid.size();
    int cols = grid.get(0).size();

    // Step 1: Collect all targets and sort by priority (e.g., value)
    List<int[]> targets = new ArrayList<>();
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (grid.get(r).get(c) > 1) {
                // Store [value, row, col]
                targets.add(new int[]{grid.get(r).get(c), r, c});
            }
        }
    }

    // Sort by value (ascending) - defines visit order
    targets.sort(Comparator.comparingInt(a -> a[0]));

    // Step 2: Sequentially visit each target using BFS
    int totalSteps = 0;
    int startR = 0, startC = 0; // Starting position

    for (int[] target : targets) {
        int targetR = target[1];
        int targetC = target[2];

        // Find shortest path from current position to next target
        int steps = bfs(grid, startR, startC, targetR, targetC);

        if (steps == -1) {
            return -1; // Target unreachable
        }

        totalSteps += steps;

        // Update starting position for next iteration
        startR = targetR;
        startC = targetC;
    }

    return totalSteps;
}

/**
 * Standard BFS to find shortest path in grid
 * Returns minimum steps from (sr, sc) to (tr, tc), or -1 if unreachable
 */
private int bfs(List<List<Integer>> grid, int sr, int sc, int tr, int tc) {
    if (sr == tr && sc == tc) return 0;

    int rows = grid.size();
    int cols = grid.get(0).size();

    Queue<int[]> queue = new LinkedList<>();
    queue.offer(new int[]{sr, sc});

    boolean[][] visited = new boolean[rows][cols];
    visited[sr][sc] = true;

    int[][] dirs = {{0,1}, {0,-1}, {1,0}, {-1,0}};
    int steps = 0;

    while (!queue.isEmpty()) {
        int size = queue.size();
        steps++;

        for (int i = 0; i < size; i++) {
            int[] cur = queue.poll();
            int r = cur[0], c = cur[1];

            for (int[] dir : dirs) {
                int nr = r + dir[0];
                int nc = c + dir[1];

                // Check bounds and obstacles
                if (nr < 0 || nr >= rows || nc < 0 || nc >= cols
                    || visited[nr][nc] || grid.get(nr).get(nc) == 0) {
                    continue;
                }

                // Found target
                if (nr == tr && nc == tc) {
                    return steps;
                }

                visited[nr][nc] = true;
                queue.offer(new int[]{nr, nc});
            }
        }
    }

    return -1; // Unreachable
}

Problem: Cut trees in forest from shortest to tallest, return minimum steps
Grid: [[1,2,3],    Trees: (0,1)=2, (0,2)=3, (1,2)=4, (2,0)=7, (2,1)=6, (2,2)=5
       [0,0,4],    Sorted: 2→3→4→5→6→7
       [7,6,5]]

Path: (0,0) →[1 step]→ (0,1) cut 2
      (0,1) →[2 steps]→ (0,2) cut 3
      (0,2) →[1 step]→ (1,2) cut 4
      (1,2) →[1 step]→ (2,2) cut 5
      (2,2) →[1 step]→ (2,1) cut 6
      (2,1) →[1 step]→ (2,0) cut 7
Total: 1+2+1+1+1+1 = 7 steps (Note: Problem statement has different expected output)

Key insight: Must cut in sorted order, BFS finds shortest path between each pair