BFS — 進階變形

# python
# LC 934 - Shortest Bridge
# IDEA: flood-fill island A (mark 2, enqueue every cell), then multi-source BFS over water to island B
# time = O(n^2), space = O(n^2)   each cell is marked once by the fill and once by the BFS
from collections import deque

def shortestBridge(grid):
    n = len(grid)
    queue = deque()

    def mark(r, c):                        # iterative flood fill: no recursion limit
        stack = [(r, c)]
        grid[r][c] = 2
        while stack:
            r, c = stack.pop()
            queue.append((r, c))           # every cell of island A is a source
            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                nr, nc = r + dr, c + dc
                if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 1:
                    grid[nr][nc] = 2
                    stack.append((nr, nc))

    first = next((r, c) for r in range(n) for c in range(n) if grid[r][c] == 1)
    mark(*first)
    flips = 0
    while queue:
        for _ in range(len(queue)):
            r, c = queue.popleft()
            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                nr, nc = r + dr, c + dc
                if not (0 <= nr < n and 0 <= nc < n) or grid[nr][nc] == 2:
                    continue
                if grid[nr][nc] == 1:
                    return flips           # touched island B
                grid[nr][nc] = 2           # water is now part of the bridge frontier
                queue.append((nr, nc))
        flips += 1
    return -1

// java
// LC 934 - Shortest Bridge
// IDEA: DFS marks the first island and enqueues all of it; BFS over water until island B is touched
// time = O(n^2), space = O(n^2)
public int shortestBridge(int[][] grid) {
    int n = grid.length;
    Queue<int[]> queue = new LinkedList<>();
    boolean found = false;
    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;
            }
        }
    }
    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], 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 the second island
                    if (grid[ny][nx] == 0) queue.add(new int[]{nx, ny});
                }
            }
        }
        steps++;
    }
    return -1;
}

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;                       // part of the first island
    queue.add(new int[]{x, y});
    dfsMarkIsland(grid, x + 1, y, queue);
    dfsMarkIsland(grid, x - 1, y, queue);
    dfsMarkIsland(grid, x, y + 1, queue);
    dfsMarkIsland(grid, x, y - 1, queue);
}

grid = [[0,1],      fill marks (0,1) as 2, queue = [(0,1)]
        [1,0]]
level 0 (flips = 0): (0,1) -> water (0,0), (1,1) enqueued
level 1 (flips = 1): (0,0) -> (1,0) is 1 -> return 1

# python
# LC 317 - Shortest Distance from All Buildings
# IDEA: one BFS per building with a fresh visited; add its distances into total, count who reached each cell
# time = O(k * m * n), space = O(m * n)   k = number of buildings
from collections import deque

def shortestDistance(grid):
    m, n = len(grid), len(grid[0])
    total = [[0] * n for _ in range(m)]    # summed distance from every building so far
    reach = [[0] * n for _ in range(m)]    # how many buildings reached this cell
    buildings = 0
    for sr in range(m):
        for sc in range(n):
            if grid[sr][sc] != 1:
                continue
            buildings += 1
            seen = [[False] * n for _ in range(m)]     # fresh for every building
            queue = deque([(sr, sc)])
            seen[sr][sc] = True
            dist = 0
            while queue:
                dist += 1
                for _ in range(len(queue)):
                    r, c = queue.popleft()
                    for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                        nr, nc = r + dr, c + dc
                        if 0 <= nr < m and 0 <= nc < n and not seen[nr][nc] and grid[nr][nc] == 0:
                            seen[nr][nc] = True
                            total[nr][nc] += dist
                            reach[nr][nc] += 1
                            queue.append((nr, nc))
    return min((total[r][c] for r in range(m) for c in range(n)
                if grid[r][c] == 0 and reach[r][c] == buildings), default=-1)

// java
// LC 317 - Shortest Distance from All Buildings
// IDEA: independent BFS per building, fresh visited each; accumulate distance and reach count
// time = O(k * m * n), space = O(m * n)
public int shortestDistance(int[][] grid) {
    int rows = grid.length, cols = grid[0].length;
    int[][] totalDist = new int[rows][cols];
    int[][] reachCount = new int[rows][cols];
    int buildingCount = 0;
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (grid[r][c] == 1) {
                buildingCount++;
                boolean[][] visited = new boolean[rows][cols];   // fresh for this building
                bfsSingleSource(grid, r, c, visited, totalDist, reachCount);
            }
        }
    }
    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;
}

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();
            for (int[] d : dirs) {
                int nr = cur[0] + d[0], nc = cur[1] + 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;
                    totalDist[nr][nc] += dist;
                    reachCount[nr][nc]++;
                    queue.offer(new int[]{nr, nc});
                }
            }
        }
    }
}

# python
# LC 815 - Bus Routes
# IDEA: BFS over routes; a stop links every route through it; level = buses taken
# time = O(sum of route lengths), space = O(sum of route lengths)
from collections import defaultdict, deque

def numBusesToDestination(routes, source, target):
    if source == target:
        return 0
    stop_to_routes = defaultdict(list)
    for i, route in enumerate(routes):
        for stop in route:
            stop_to_routes[stop].append(i)
    queue = deque()
    used_routes = set()
    for r in stop_to_routes[source]:       # every bus through the source is ride 1
        queue.append(r)
        used_routes.add(r)
    seen_stops = {source}
    buses = 1
    while queue:
        for _ in range(len(queue)):
            route = queue.popleft()
            for stop in routes[route]:
                if stop == target:
                    return buses
                if stop in seen_stops:
                    continue               # this stop's transfers were already enqueued
                seen_stops.add(stop)
                for nxt in stop_to_routes[stop]:
                    if nxt not in used_routes:
                        used_routes.add(nxt)
                        queue.append(nxt)
        buses += 1
    return -1

// java
// LC 815 - Bus Routes
// IDEA: build stop -> routes; BFS on route ids with two visited sets (routes and stops)
// time = O(sum of route lengths), space = O(sum of route lengths)
public int numBusesToDestination(int[][] routes, int source, int target) {
    if (source == target) return 0;
    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);
    Queue<Integer> queue = new LinkedList<>();
    Set<Integer> visitedRoutes = new HashSet<>();
    Set<Integer> visitedStops = new HashSet<>();
    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();
            for (int stop : routes[currRoute]) {
                if (stop == target) return busCount;
                if (!visitedStops.add(stop)) continue;
                for (int nextRoute : stopToRoutes.getOrDefault(stop, new ArrayList<>())) {
                    if (visitedRoutes.add(nextRoute)) queue.offer(nextRoute);
                }
            }
        }
        busCount++;
    }
    return -1;
}

routes = [[1,2,7],[3,6,7]], source = 1, target = 6
stop -> routes: 1:[0] 2:[0] 7:[0,1] 3:[1] 6:[1]
buses 1: route 0 -> stops 1, 2, 7; stop 7 enqueues route 1
buses 2: route 1 -> stop 3, stop 6 == target -> return 2

# python
# LC 126 - Word Ladder II
# IDEA: level BFS records parents[word] = every word one level above it; DFS back from endWord
# time = O(N * L * 26 + paths * L), space = O(N * L)   N words of length L; output not counted
from collections import defaultdict

def findLadders(beginWord, endWord, wordList):
    words = set(wordList)
    if endWord not in words:
        return []
    parents = defaultdict(list)
    level = {beginWord}
    words.discard(beginWord)
    found = False
    while level and not found:
        words -= level                     # remove the WHOLE level only after it is built
        next_level = set()
        for word in level:
            for i in range(len(word)):
                for ch in 'abcdefghijklmnopqrstuvwxyz':
                    nxt = word[:i] + ch + word[i + 1:]
                    if nxt in words:
                        if nxt == endWord:
                            found = True   # finish this level, never build the next
                        next_level.add(nxt)
                        parents[nxt].append(word)
        level = next_level
    if not found:
        return []

    paths, path = [], [endWord]

    def walk(word):                        # DFS from endWord back to beginWord
        if word == beginWord:
            paths.append(path[::-1])
            return
        for p in parents[word]:
            path.append(p)
            walk(p)
            path.pop()

    walk(endWord)
    return paths

// java
// LC 126 - Word Ladder II
// IDEA: BFS records every predecessor at the shortest distance; DFS from endWord enumerates the DAG
// time = O(N * L * 26 + paths * L), space = O(N * L)
public List<List<String>> findLadders(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<String, List<String>> parents = new HashMap<>();
    Map<String, Integer> distances = new HashMap<>();
    Queue<String> queue = new LinkedList<>();
    queue.add(beginWord);
    distances.put(beginWord, 0);
    boolean found = false;
    while (!queue.isEmpty() && !found) {
        int size = queue.size();
        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 = 'a'; c <= 'z'; c++) {
                    if (c == original) continue;
                    chars[j] = c;
                    String nextWord = new String(chars);
                    if (!wordSet.contains(nextWord)) continue;
                    int newDistance = distances.get(word) + 1;
                    if (!distances.containsKey(nextWord)) {             // first time: enqueue once
                        distances.put(nextWord, newDistance);
                        parents.computeIfAbsent(nextWord, k -> new ArrayList<>()).add(word);
                        queue.add(nextWord);
                        if (nextWord.equals(endWord)) found = true;
                    } else if (distances.get(nextWord) == newDistance) {  // another shortest parent
                        parents.get(nextWord).add(word);
                    }
                }
                chars[j] = original;
            }
        }
    }
    if (distances.containsKey(endWord)) {
        dfsEnumeratePaths(endWord, beginWord, parents, new LinkedList<>(), result);
    }
    return result;
}

private void dfsEnumeratePaths(String current, String beginWord, Map<String, List<String>> parents,
                               List<String> path, List<List<String>> result) {
    path.add(0, current);                 // building the path backwards
    if (current.equals(beginWord)) {
        result.add(new ArrayList<>(path));
    } else {
        for (String prev : parents.getOrDefault(current, new ArrayList<>())) {
            dfsEnumeratePaths(prev, beginWord, parents, path, result);
        }
    }
    path.remove(0);
}

hit -> cog, words = [hot, dot, dog, lot, log, cog]
level 1: hot            parents[hot] = [hit]
level 2: dot, lot       parents[dot] = [hot], parents[lot] = [hot]
level 3: dog, log       parents[dog] = [dot], parents[log] = [lot]
level 4: cog            parents[cog] = [dog, log]   <- two parents on one level: found, stop
DFS from cog: cog<-dog<-dot<-hot<-hit  and  cog<-log<-lot<-hot<-hit

# python
# LC 1087 - Brace Expansion
# IDEA: parse into groups, sort each; level i = every prefix extended by every option of group i
# time = O(G * |result| * L), space = O(|result| * L)   G groups, L = output word length
def expand(s):
    groups = []
    i = 0
    while i < len(s):
        if s[i] == '{':
            j = s.index('}', i)
            groups.append(sorted(s[i + 1:j].split(',')))   # sorted -> output is sorted
            i = j + 1
        else:
            groups.append([s[i]])
            i += 1
    level = [""]
    for group in groups:
        next_level = []
        for prefix in level:
            for option in group:
                next_level.append(prefix + option)
        level = next_level
    return level

// java
// LC 1087 - Brace Expansion (the level loop, given the parsed groups)
// IDEA: snapshot the queue size, extend every prefix of this level by every option of the group
// time = O(G * |result| * L), space = O(|result| * L)
public String[] cartesianBFS(List<List<String>> groups) {
    Queue<String> queue = new LinkedList<>();
    queue.add("");                        // one empty prefix at depth 0
    for (List<String> group : groups) {
        int size = queue.size();          // snapshot the current level
        for (int k = 0; k < size; k++) {
            String prefix = queue.poll();
            for (String option : group) queue.add(prefix + option);
        }
    }
    return queue.toArray(new String[0]);
}

s = "{a,b}c{d,e}f"   groups = [[a,b], [c], [d,e], [f]]
level 0: [""]
level 1: [a, b]
level 2: [ac, bc]
level 3: [acd, ace, bcd, bce]
level 4: [acdf, acef, bcdf, bcef]   <- the answer, already sorted

# python
# LC 301 - Remove Invalid Parentheses
# IDEA: level = number of deletions; return the first level that has valid strings
# time = O(2^n * n), space = O(n * 2^n)   up to 2^n strings of length n in one level
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 [""]

// java
// LC 301 - Remove Invalid Parentheses
// IDEA: 1 BFS level = 1 deletion. First level containing a valid string is the answer level.
// time = O(2^n * n), space = O(n * 2^n)   up to 2^n strings of length n in one 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;
}

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

# 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 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];   // the mask is part of the visited 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 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*k)   the queue's worst case; best[][] itself is 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

// 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*k)   the queue's worst case; best[][] itself is 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
                // `<=`, not `<`: an equal budget arriving no earlier 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 1368 - Minimum Cost to Make at Least One Valid Path in a Grid
# IDEA: deque BFS - appendleft for 0-cost moves, append for 1-cost moves
# time = O(m*n), space = O(m*n)
from collections import deque

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]

// java
// LC 1368 - Minimum Cost to Make at Least One Valid Path in a Grid
// IDEA: 0-1 BFS. Following grid[r][c]'s arrow costs 0 -> push FRONT; turning costs 1 -> push BACK.
// time = O(m*n), space = O(m*n)
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 127 - Word Ladder (bidirectional)
# IDEA: two frontier sets; expand the smaller one level at a time; a neighbour in the other set ends it
# time = O(N * L^2 * 26) worst case (each candidate is an O(L) string to build and hash), space = O(N * L)
def ladderLength(beginWord, endWord, wordList):
    words = set(wordList)
    if endWord not in words:
        return 0
    front, back = {beginWord}, {endWord}
    words.discard(beginWord)
    length = 1                             # words on the path so far
    while front and back:
        if len(front) > len(back):
            front, back = back, front      # always grow the smaller side
        next_front = set()
        for word in front:
            for i in range(len(word)):
                for ch in 'abcdefghijklmnopqrstuvwxyz':
                    nxt = word[:i] + ch + word[i + 1:]
                    if nxt in back:
                        return length + 1  # the two searches meet
                    if nxt in words:
                        words.discard(nxt) # mark on enqueue, shared by both sides
                        next_front.add(nxt)
        front = next_front
        length += 1
    return 0

# python
# LC 675 - Cut Off Trees for Golf Event
# IDEA: sort trees by height; total = sum of grid-BFS distances between consecutive trees
# time = O(t * m * n), space = O(m * n)   t = number of trees, one BFS each
from collections import deque

def cutOffTree(forest):
    m, n = len(forest), len(forest[0])
    trees = sorted((forest[r][c], r, c) for r in range(m) for c in range(n) if forest[r][c] > 1)

    def bfs(sr, sc, tr, tc):
        if (sr, sc) == (tr, tc):
            return 0
        queue = deque([(sr, sc)])
        seen = {(sr, sc)}
        steps = 0
        while queue:
            steps += 1
            for _ in range(len(queue)):
                r, c = queue.popleft()
                for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < m and 0 <= nc < n and (nr, nc) not in seen and forest[nr][nc] != 0:
                        if (nr, nc) == (tr, tc):
                            return steps
                        seen.add((nr, nc))
                        queue.append((nr, nc))
        return -1

    total = 0
    r, c = 0, 0
    for _, tr, tc in trees:
        steps = bfs(r, c, tr, tc)
        if steps == -1:
            return -1                      # one unreachable tree fails the whole walk
        total += steps
        r, c = tr, tc
    return total

// java
// LC 675 - Cut Off Trees for Golf Event
// IDEA: sort the targets by height, then one BFS per consecutive pair; sum the distances
// time = O(t * m * n), space = O(m * n)
public int cutOffTree(List<List<Integer>> grid) {
    int rows = grid.size(), cols = grid.get(0).size();
    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) targets.add(new int[]{grid.get(r).get(c), r, c});
    targets.sort((a, b) -> Integer.compare(a[0], b[0]));
    int totalSteps = 0, startR = 0, startC = 0;
    for (int[] target : targets) {
        int steps = bfs(grid, startR, startC, target[1], target[2]);
        if (steps == -1) return -1;
        totalSteps += steps;
        startR = target[1];
        startC = target[2];
    }
    return totalSteps;
}

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(), 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();
            for (int[] dir : dirs) {
                int nr = cur[0] + dir[0], nc = cur[1] + dir[1];
                if (nr < 0 || nr >= rows || nc < 0 || nc >= cols
                        || visited[nr][nc] || grid.get(nr).get(nc) == 0) continue;
                if (nr == tr && nc == tc) return steps;
                visited[nr][nc] = true;
                queue.offer(new int[]{nr, nc});
            }
        }
    }
    return -1;
}

forest = [[1,2,3],    trees by height: 2 (0,1), 3 (0,2), 4 (1,2), 5 (2,2), 6 (2,1), 7 (2,0)
          [0,0,4],
          [7,6,5]]
(0,0)->(0,1) 1 · (0,1)->(0,2) 1 · (0,2)->(1,2) 1 · (1,2)->(2,2) 1 · (2,2)->(2,1) 1 · (2,1)->(2,0) 1
total = 6