网格遍历与多源搜索

def island_stats(grid: list[list[int]]) -> tuple[int, int]:
    """(number of islands, largest island area) in a 0/1 grid (LC 200, LC 695)."""
    rows, cols = len(grid), len(grid[0])
    seen = [[False] * cols for _ in range(rows)]
    count = best = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] != 1 or seen[r][c]:
                continue
            count += 1
            area, stack = 0, [(r, c)]
            seen[r][c] = True
            while stack:  # an explicit stack: no recursion limit on big islands
                i, j = stack.pop()
                area += 1
                for ni, nj in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
                    if 0 <= ni < rows and 0 <= nj < cols and grid[ni][nj] == 1 and not seen[ni][nj]:
                        seen[ni][nj] = True  # mark on push: no cell goes in twice
                        stack.append((ni, nj))
            best = max(best, area)
    return count, best

// {number of islands, largest island area} in a 0/1 grid (LC 200, LC 695).
pair<int, int> islandStats(const vector<vector<int>>& grid) {
    int rows = grid.size(), cols = grid[0].size(), count = 0, best = 0;
    vector<vector<bool>> seen(rows, vector<bool>(cols, false));
    int dr[] = {1, -1, 0, 0}, dc[] = {0, 0, 1, -1};
    for (int r = 0; r < rows; r++)
        for (int c = 0; c < cols; c++) {
            if (grid[r][c] != 1 || seen[r][c]) continue;
            count++;
            int area = 0;
            vector<pair<int, int>> stack{{r, c}};
            seen[r][c] = true;
            while (!stack.empty()) {  // an explicit stack: no recursion limit on big islands
                auto [i, j] = stack.back();
                stack.pop_back();
                area++;
                for (int d = 0; d < 4; d++) {
                    int ni = i + dr[d], nj = j + dc[d];
                    if (ni >= 0 && ni < rows && nj >= 0 && nj < cols && grid[ni][nj] == 1 && !seen[ni][nj]) {
                        seen[ni][nj] = true;  // mark on push: no cell goes in twice
                        stack.push_back({ni, nj});
                    }
                }
            }
            best = max(best, area);
        }
    return {count, best};
}

class Solution {
    // {number of islands, largest island area} in a 0/1 grid (LC 200, LC 695).
    int[] islandStats(int[][] grid) {
        int rows = grid.length, cols = grid[0].length, count = 0, best = 0;
        boolean[][] seen = new boolean[rows][cols];
        int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        for (int r = 0; r < rows; r++)
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] != 1 || seen[r][c]) continue;
                count++;
                int area = 0;
                Deque<int[]> stack = new ArrayDeque<>();
                stack.push(new int[] {r, c});
                seen[r][c] = true;
                while (!stack.isEmpty()) { // an explicit stack: no recursion limit on big islands
                    int[] cell = stack.pop();
                    area++;
                    for (int[] d : dirs) {
                        int ni = cell[0] + d[0], nj = cell[1] + d[1];
                        if (ni >= 0 && ni < rows && nj >= 0 && nj < cols && grid[ni][nj] == 1 && !seen[ni][nj]) {
                            seen[ni][nj] = true; // mark on push: no cell goes in twice
                            stack.push(new int[] {ni, nj});
                        }
                    }
                }
                best = Math.max(best, area);
            }
        return new int[] {count, best};
    }
}

// islandStats returns the number of islands and the largest island area in a 0/1 grid.
func islandStats(grid [][]int) (int, int) {
	rows, cols := len(grid), len(grid[0])
	seen := make([][]bool, rows)
	for r := range seen {
		seen[r] = make([]bool, cols)
	}
	count, best := 0, 0
	dirs := [][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
	for r := 0; r < rows; r++ {
		for c := 0; c < cols; c++ {
			if grid[r][c] != 1 || seen[r][c] {
				continue
			}
			count++
			area := 0
			stack := [][2]int{{r, c}}
			seen[r][c] = true
			for len(stack) > 0 { // an explicit stack: no recursion limit on big islands
				cell := stack[len(stack)-1]
				stack = stack[:len(stack)-1]
				area++
				for _, d := range dirs {
					ni, nj := cell[0]+d[0], cell[1]+d[1]
					if ni >= 0 && ni < rows && nj >= 0 && nj < cols && grid[ni][nj] == 1 && !seen[ni][nj] {
						seen[ni][nj] = true // mark on push: no cell goes in twice
						stack = append(stack, [2]int{ni, nj})
					}
				}
			}
			best = max(best, area)
		}
	}
	return count, best
}

from collections import deque


def shortest_with_breaks(grid: list[list[int]], k: int) -> int:
    """Fewest steps from top-left to bottom-right, breaking at most k walls (LC 1293)."""
    rows, cols = len(grid), len(grid[0])
    best = [[-1] * cols for _ in range(rows)]  # most breaks still in hand on reaching a cell
    best[0][0] = k
    q = deque([(0, 0, k)])  # a state is (r, c, breaks left)
    steps = 0
    while q:
        for _ in range(len(q)):  # one BFS level per step
            r, c, left = q.popleft()
            if r == rows - 1 and c == cols - 1:
                return steps
            for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
                if 0 <= nr < rows and 0 <= nc < cols:
                    rest = left - grid[nr][nc]
                    if rest > best[nr][nc]:  # more breaks left than any earlier visit: worth it
                        best[nr][nc] = rest
                        q.append((nr, nc, rest))
        steps += 1
    return -1

// Fewest steps from top-left to bottom-right, breaking at most k walls (LC 1293).
int shortestWithBreaks(const vector<vector<int>>& grid, int k) {
    int rows = grid.size(), cols = grid[0].size();
    vector<vector<int>> best(rows, vector<int>(cols, -1));  // most breaks still in hand on reaching a cell
    best[0][0] = k;
    queue<array<int, 3>> q;  // a state is {r, c, breaks left}
    q.push({0, 0, k});
    int dr[] = {1, -1, 0, 0}, dc[] = {0, 0, 1, -1};
    for (int steps = 0; !q.empty(); steps++)
        for (int n = q.size(); n > 0; n--) {  // one BFS level per step
            auto [r, c, left] = q.front();
            q.pop();
            if (r == rows - 1 && c == cols - 1) return steps;
            for (int d = 0; d < 4; d++) {
                int nr = r + dr[d], nc = c + dc[d];
                if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
                int rest = left - grid[nr][nc];
                if (rest > best[nr][nc]) {  // more breaks left than any earlier visit: worth it
                    best[nr][nc] = rest;
                    q.push({nr, nc, rest});
                }
            }
        }
    return -1;
}

class Solution {
    // Fewest steps from top-left to bottom-right, breaking at most k walls (LC 1293).
    int shortestWithBreaks(int[][] grid, int k) {
        int rows = grid.length, cols = grid[0].length;
        int[][] best = new int[rows][cols]; // most breaks still in hand on reaching a cell
        for (int[] row : best) Arrays.fill(row, -1);
        best[0][0] = k;
        Deque<int[]> q = new ArrayDeque<>(); // a state is {r, c, breaks left}
        q.offer(new int[] {0, 0, k});
        int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        for (int steps = 0; !q.isEmpty(); steps++)
            for (int n = q.size(); n > 0; n--) { // one BFS level per step
                int[] s = q.poll();
                if (s[0] == rows - 1 && s[1] == cols - 1) return steps;
                for (int[] d : dirs) {
                    int nr = s[0] + d[0], nc = s[1] + d[1];
                    if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
                    int rest = s[2] - grid[nr][nc];
                    if (rest > best[nr][nc]) { // more breaks left than any earlier visit: worth it
                        best[nr][nc] = rest;
                        q.offer(new int[] {nr, nc, rest});
                    }
                }
            }
        return -1;
    }
}

// shortestWithBreaks returns the fewest steps from top-left to bottom-right, breaking at most k walls.
func shortestWithBreaks(grid [][]int, k int) int {
	rows, cols := len(grid), len(grid[0])
	best := make([][]int, rows) // most breaks still in hand on reaching a cell
	for r := range best {
		best[r] = make([]int, cols)
		for c := range best[r] {
			best[r][c] = -1
		}
	}
	best[0][0] = k
	q := [][3]int{{0, 0, k}} // a state is {r, c, breaks left}
	dirs := [][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
	for steps := 0; len(q) > 0; steps++ {
		var next [][3]int // the following BFS level
		for _, s := range q {
			if s[0] == rows-1 && s[1] == cols-1 {
				return steps
			}
			for _, d := range dirs {
				nr, nc := s[0]+d[0], s[1]+d[1]
				if nr < 0 || nr >= rows || nc < 0 || nc >= cols {
					continue
				}
				if rest := s[2] - grid[nr][nc]; rest > best[nr][nc] { // more breaks left than before: worth it
					best[nr][nc] = rest
					next = append(next, [3]int{nr, nc, rest})
				}
			}
		}
		q = next
	}
	return -1
}