给你一个下标从 1 开始的二进制矩阵，其中 0 表示陆地，1 表示水域。同时给你 row 和 col 分别表示矩阵中行和列的数目。

一开始在第 0 天，整个 矩阵都是 陆地 。但每一天都会有一块新陆地被 水 淹没变成水域。给你一个下标从 1 开始的二维数组 cells ，其中 cells[i] = [ri, ci] 表示在第 i 天，第 ri 行 ci 列（下标都是从 1 开始）的陆地会变成 水域 （也就是 0 变成 1 ）。

你想知道从矩阵最 上面 一行走到最 下面 一行，且只经过陆地格子的 最后一天 是哪一天。你可以从最上面一行的 任意 格子出发，到达最下面一行的 任意 格子。你只能沿着 四个 基本方向移动（也就是上下左右）。

请返回只经过陆地格子能从最 上面 一行走到最 下面 一行的 最后一天 。

 

示例 1：

输入：row = 2, col = 2, cells = [[1,1],[2,1],[1,2],[2,2]]
输出：2
解释：上图描述了矩阵从第 0 天开始是如何变化的。
可以从最上面一行到最下面一行的最后一天是第 2 天。

示例 2：

输入：row = 2, col = 2, cells = [[1,1],[1,2],[2,1],[2,2]]
输出：1
解释：上图描述了矩阵从第 0 天开始是如何变化的。
可以从最上面一行到最下面一行的最后一天是第 1 天。

示例 3：

输入：row = 3, col = 3, cells = [[1,2],[2,1],[3,3],[2,2],[1,1],[1,3],[2,3],[3,2],[3,1]]
输出：3
解释：上图描述了矩阵从第 0 天开始是如何变化的。
可以从最上面一行到最下面一行的最后一天是第 3 天。

 

提示：

• 2 <= row, col <= 2 * 104
• 4 <= row * col <= 2 * 104
• cells.length == row * col
• 1 <= ri <= row
• 1 <= ci <= col
• cells 中的所有格子坐标都是 唯一 的。

解题思路

逆序，从上至下，四连通

逆序遍历所有水域cells，即从从全水域逐渐增加陆地，如果陆地在最上侧（第一行）或四连通内的区域在可连通visited内，则丢入可连通visited，否则丢入wait暂未连通。若当前可连通，基于四连通dfs来尝试取出wait内的陆地。直至可以连通至最后一行。

当然也可以采用并查集来解决该问题，但该问题可以通过增加一个cache集合来简化解法。

正序，从左至右，八连通

转换思路，“从上至下不存在路径”即为“从左至右存在一条连通水路”，这条水路可以分割为上下两片完全独立不互通的陆地。

这样问题处理起来简单很多，正序遍历所有水域cells，如果水域在最左侧（第一列）或九宫格内的区域在可连通visited内，则丢入可连通visited，否则丢入wait暂未连通。若当前可连通，基于九宫格dfs来尝试取出wait内的水域。直至可以连通至最后一列。

两种写法几乎一致，主要区别是陆地连通是四连通（上下左右），水域连通是八连通（九宫格）。

复杂度分析

时间/空间复杂度：$O(row * col)$

代码

class Solution:
    def latestDayToCross(self, row: int, col: int, cells: List[List[int]]) -> int:
        # 正序，从左至右，八连通
        dirs = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]
        # 最左侧出发可连通水域
        visited = set()
        # 最左侧出发暂未连通水域
        wait = set()
        # 增加连通水域，根据九宫格dfs
        def dfs(x, y):
            if y == col:
                return True
            for xx, yy in dirs:
                new_x, new_y = x + xx, y + yy
                if (new_x, new_y) in wait:
                    wait.remove((new_x, new_y))
                    visited.add((new_x, new_y))
                    if dfs(new_x, new_y):
                        return True
            return False
        # 依此遍历cells
        for i, (x, y) in enumerate(cells):
            flag = False
            # 最左侧出发
            if y == 1:
                flag = True
            # 非最左侧，根据九宫格判断能否连通
            else:
                for xx, yy in dirs:
                    new_x, new_y = x + xx, y + yy
                    if (new_x, new_y) in visited:
                        flag = True
                        break
            # 若当前水域可连通，则通过dfs尝试取出wait内的水域
            if flag:
                visited.add((x, y))
                if dfs(x, y):
                    return i
            # 暂未连通，丢入wait
            else:
                wait.add((x, y))

class Solution {
public:
    // 正序，从左至右，八连通
    int dirs[8][2] = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
    // 最左侧出发可连通水域
    set<pair<int, int>> visited;
    // 最左侧出发暂未连通水域
    set<pair<int, int>> wait;
    // 增加连通水域，根据九宫格dfs
    bool dfs(int x, int y, int col){
        if (y == col) return true;
        for(int i = 0; i < 8; i++){
            int new_x = x + dirs[i][0], new_y = y + dirs[i][1];
            if (wait.find(make_pair(new_x, new_y)) != wait.end()){
                wait.erase(make_pair(new_x, new_y));
                visited.insert(make_pair(new_x, new_y));
                if (dfs(new_x, new_y, col)) return true;
            }
        }
        return false;
    }
    int latestDayToCross(int row, int col, vector<vector<int>>& cells) {
        // 依此遍历cells
        for(int d = 0; d < row * col; d++){
            int x = cells[d][0], y = cells[d][1];
            bool flag = false;
            // 最左侧出发
            if (y == 1) flag = true;
            // 非最左侧，根据九宫格判断能否连通
            else{
                for(int i = 0; i < 8; i++){
                    int new_x = x + dirs[i][0], new_y = y + dirs[i][1];
                    if (visited.find(make_pair(new_x, new_y)) != visited.end()){
                        flag = true;
                        break;
                    }
                }
            }
            // 若当前水域可连通，则通过dfs尝试取出wait内的水域
            if (flag){
                visited.insert(make_pair(x, y));
                if (dfs(x, y, col)) return d;
            }
            // 暂未连通，丢入wait
            else{
                wait.insert(make_pair(x, y));
            }
        }
        // 不可能
        return -1;
    }
};

class Solution:
    def latestDayToCross(self, row: int, col: int, cells: List[List[int]]) -> int:
        # 逆序，从上至下，四连通
        dirs = [(-1, 0), (0, -1), (0, 1), (1, 0)]
        # 最上侧出发可连通陆地
        visited = set()
        # 最上侧出发暂未连通陆地
        wait = set()
        # 增加连通陆地，根据四连通dfs
        def dfs(x, y):
            if x == row:
                return True
            for xx, yy in dirs:
                new_x, new_y = x + xx, y + yy
                if (new_x, new_y) in wait:
                    wait.remove((new_x, new_y))
                    visited.add((new_x, new_y))
                    if dfs(new_x, new_y):
                        return True
            return False
        # 依此遍历cells
        for i, (x, y) in list(enumerate(cells))[::-1]:
            print(i, x, y)
            flag = False
            # 最上侧出发
            if x == 1:
                flag = True
            # 非最上侧，根据四连通判断能否连通
            else:
                for xx, yy in dirs:
                    new_x, new_y = x + xx, y + yy
                    if (new_x, new_y) in visited:
                        flag = True
                        break
            # 若当前陆地可连通，则通过dfs尝试取出wait内的陆地
            if flag:
                visited.add((x, y))
                if dfs(x, y):
                    return i
            # 暂未连通，丢入wait
            else:
                wait.add((x, y))

前言

本题和 1631. 最小体力消耗路径 是几乎一样的题目。

方法一：二分查找 + 广度优先搜索

思路与算法

如果第 $k$ 天我们能够从最上面一行走到最下面一行，那么第 $0, 1, \cdots, k-1$ 天我们也可以。

因此，一定存在一个最大值 $k'$ 使得：

• 当 $k \leq k'$ 时，我们可以在第 $k$ 天从最上面一行走到最下面一行；

• 当 $k > k'$ 时，我们不可以在第 $k$ 天从最上面一行走到最下面一行。

我们可以使用二分查找的方法找出 $k'$。二分查找的下界为 $0$，上界为 $\textit{row} \times \textit{col}$。

在二分查找的每一步中，我们需要对于二分到的 $k$ 值，判断是否可以最上面一行走到最下面一行。一种可行的方法是，我们构造一个 $\textit{row} \times \textit{col}$ 的全 $1$ 矩阵，并把 $\textit{cells}$ 中前 $k$ 个坐标在矩阵中对应的格子置为 $0$。随后，我们将第一行的所有格子（如果格子上的值为 $1$）放入队列中，进行广度优先搜索，搜索的过程中只能走向上下左右相邻并且值为 $1$ 的格子。如果能够搜索到最后一行的某个格子，那么说明存在一条从最上面一行走到最下面一行的路径，我们修改二分的下界，否则修改二分的上界。

代码

###C++

class Solution {
private:
    static constexpr int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

public:
    int latestDayToCross(int row, int col, vector<vector<int>>& cells) {
        int left = 0, right = row * col, ans = 0;
        while (left <= right) {
            int mid = (left + right) / 2;
            
            vector<vector<int>> grid(row, vector<int>(col, 1));
            for (int i = 0; i < mid; ++i) {
                grid[cells[i][0] - 1][cells[i][1] - 1] = 0;
            }

            queue<pair<int, int>> q;
            for (int i = 0; i < col; ++i) {
                if (grid[0][i]) {
                    q.emplace(0, i);
                    grid[0][i] = 0;
                }
            }
            bool found = false;
            while (!q.empty()) {
                auto [x, y] = q.front();
                q.pop();
                for (int d = 0; d < 4; ++d) {
                    int nx = x + dirs[d][0];
                    int ny = y + dirs[d][1];
                    if (nx >= 0 && nx < row && ny >= 0 && ny < col && grid[nx][ny]) {
                        if (nx == row - 1) {
                            found = true;
                            break;
                        }
                        q.emplace(nx, ny);
                        grid[nx][ny] = 0;
                    }
                }
            }
            if (found) {
                ans = mid;
                left = mid + 1;
            }
            else {
                right = mid - 1;
            }
        }
        return ans;
    }
};

###Python

class Solution:
    def latestDayToCross(self, row: int, col: int, cells: List[List[int]]) -> int:
        left, right, ans = 0, row * col, 0
        while left <= right:
            mid = (left + right) // 2
            
            grid = [[1] * col for _ in range(row)]
            for x, y in cells[:mid]:
                grid[x - 1][y - 1] = 0

            q = deque()
            for i in range(col):
                if grid[0][i]:
                    q.append((0, i))
                    grid[0][i] = 0
            
            found = False
            while q:
                x, y = q.popleft()
                for nx, ny in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
                    if 0 <= nx < row and 0 <= ny < col and grid[nx][ny]:
                        if nx == row - 1:
                            found = True
                            break
                        q.append((nx, ny))
                        grid[nx][ny] = 0
            
            if found:
                ans = mid
                left = mid + 1
            else:
                right = mid - 1
        
        return ans

###Java

class Solution {
    private static final int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    public int latestDayToCross(int row, int col, int[][] cells) {
        int left = 0, right = row * col, ans = 0;
        while (left <= right) {
            int mid = (left + right) / 2;
            int[][] grid = new int[row][col];
            for (int i = 0; i < row; i++) {
                Arrays.fill(grid[i], 1);
            }
            for (int i = 0; i < mid; i++) {
                grid[cells[i][0] - 1][cells[i][1] - 1] = 0;
            }

            Queue<int[]> q = new LinkedList<>();
            for (int i = 0; i < col; i++) {
                if (grid[0][i] == 1) {
                    q.offer(new int[]{0, i});
                    grid[0][i] = 0;
                }
            }
            
            boolean found = false;
            while (!q.isEmpty()) {
                int[] cell = q.poll();
                int x = cell[0], y = cell[1];
                for (int[] dir : dirs) {
                    int nx = x + dir[0];
                    int ny = y + dir[1];
                    if (nx >= 0 && nx < row && ny >= 0 && ny < col && grid[nx][ny] == 1) {
                        if (nx == row - 1) {
                            found = true;
                            break;
                        }
                        q.offer(new int[]{nx, ny});
                        grid[nx][ny] = 0;
                    }
                }
                if (found) {
                    break;
                }
            }
            
            if (found) {
                ans = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return ans;
    }
}

###C#

public class Solution {
    private static readonly int[][] dirs = new int[][] {
        new int[] {-1, 0}, new int[] {1, 0}, new int[] {0, -1}, new int[] {0, 1}
    };

    public int LatestDayToCross(int row, int col, int[][] cells) {
        int left = 0, right = row * col, ans = 0;
        while (left <= right) {
            int mid = (left + right) / 2;
            
            int[][] grid = new int[row][];
            for (int i = 0; i < row; i++) {
                grid[i] = new int[col];
                Array.Fill(grid[i], 1);
            }
            for (int i = 0; i < mid; i++) {
                grid[cells[i][0] - 1][cells[i][1] - 1] = 0;
            }

            Queue<int[]> q = new Queue<int[]>();
            for (int i = 0; i < col; i++) {
                if (grid[0][i] == 1) {
                    q.Enqueue(new int[] {0, i});
                    grid[0][i] = 0;
                }
            }
            
            bool found = false;
            while (q.Count > 0) {
                int[] cell = q.Dequeue();
                int x = cell[0], y = cell[1];
                foreach (var dir in dirs) {
                    int nx = x + dir[0];
                    int ny = y + dir[1];
                    if (nx >= 0 && nx < row && ny >= 0 && ny < col && grid[nx][ny] == 1) {
                        if (nx == row - 1) {
                            found = true;
                            break;
                        }
                        q.Enqueue(new int[] {nx, ny});
                        grid[nx][ny] = 0;
                    }
                }
                if (found) {
                    break;
                }
            }
            
            if (found) {
                ans = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return ans;
    }
}

###Go

func latestDayToCross(row int, col int, cells [][]int) int {
    dirs := [4][2]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
    left, right, ans := 0, row * col, 0

    for left <= right {
        mid := (left + right) / 2
        grid := make([][]int, row)
        for i := range grid {
            grid[i] = make([]int, col)
            for j := range grid[i] {
                grid[i][j] = 1
            }
        }
        for i := 0; i < mid; i++ {
            grid[cells[i][0] - 1][cells[i][1] - 1] = 0
        }
        
        queue := [][2]int{}
        for i := 0; i < col; i++ {
            if grid[0][i] == 1 {
                queue = append(queue, [2]int{0, i})
                grid[0][i] = 0
            }
        }
        
        found := false
        for len(queue) > 0 {
            cell := queue[0]
            queue = queue[1:]
            x, y := cell[0], cell[1]
            
            for _, dir := range dirs {
                nx, ny := x+dir[0], y+dir[1]
                if nx >= 0 && nx < row && ny >= 0 && ny < col && grid[nx][ny] == 1 {
                    if nx == row-1 {
                        found = true
                        break
                    }
                    queue = append(queue, [2]int{nx, ny})
                    grid[nx][ny] = 0
                }
            }
            if found {
                break
            }
        }
        
        if found {
            ans = mid
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    
    return ans
}

###C

typedef struct {
    int x;
    int y;
} Point;

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

int latestDayToCross(int row, int col, int** cells, int cellsSize, int* cellsColSize) {
    int left = 0, right = row * col, ans = 0;
    int grid[row][col];
    Point queue[row * col];

    while (left <= right) {
        int mid = (left + right) / 2;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                grid[i][j] = 1;
            }
        }
        for (int i = 0; i < mid; i++) {
            grid[cells[i][0] - 1][cells[i][1] - 1] = 0;
        }        
        int front = 0, rear = 0;
        for (int i = 0; i < col; i++) {
            if (grid[0][i] == 1) {
                queue[rear++] = (Point){0, i};
                grid[0][i] = 0;
            }
        }
        
        bool found = false;
        while (front < rear) {
            Point cell = queue[front++];
            int x = cell.x, y = cell.y;
            for (int d = 0; d < 4; d++) {
                int nx = x + dirs[d][0];
                int ny = y + dirs[d][1];
                if (nx >= 0 && nx < row && ny >= 0 && ny < col && grid[nx][ny] == 1) {
                    if (nx == row - 1) {
                        found = true;
                        break;
                    }
                    queue[rear++] = (Point){nx, ny};
                    grid[nx][ny] = 0;
                }
            }
            if (found) {
                break;
            }
        }

        if (found) {
            ans = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return ans;
}

###JavaScript

var latestDayToCross = function(row, col, cells) {
    const dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]];
        
    let left = 0, right = row * col, ans = 0;
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        const grid = Array.from({length: row}, () => 
            Array.from({length: col}, () => 1));
        for (let i = 0; i < mid; i++) {
            grid[cells[i][0] - 1][cells[i][1] - 1] = 0;
        }
        
        const queue = [];
        for (let i = 0; i < col; i++) {
            if (grid[0][i] === 1) {
                queue.push([0, i]);
                grid[0][i] = 0;
            }
        }
        
        let found = false;
        while (queue.length > 0) {
            const [x, y] = queue.shift();
            for (const [dx, dy] of dirs) {
                const nx = x + dx;
                const ny = y + dy;
                if (nx >= 0 && nx < row && ny >= 0 && ny < col && grid[nx][ny] === 1) {
                    if (nx === row - 1) {
                        found = true;
                        break;
                    }
                    queue.push([nx, ny]);
                    grid[nx][ny] = 0;
                }
            }
            if (found) break;
        }
        
        if (found) {
            ans = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return ans;
};

###TypeScript

function latestDayToCross(row: number, col: number, cells: number[][]): number {
    const dirs: number[][] = [[-1, 0], [1, 0], [0, -1], [0, 1]];
    let left = 0, right = row * col, ans = 0;
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        const grid: number[][] = Array.from({length: row}, () => 
            Array.from({length: col}, () => 1));
        for (let i = 0; i < mid; i++) {
            grid[cells[i][0] - 1][cells[i][1] - 1] = 0;
        }
        
        const queue: number[][] = [];
        for (let i = 0; i < col; i++) {
            if (grid[0][i] === 1) {
                queue.push([0, i]);
                grid[0][i] = 0;
            }
        }
        let found = false;
        while (queue.length > 0) {
            const [x, y] = queue.shift()!;
            for (const [dx, dy] of dirs) {
                const nx = x + dx;
                const ny = y + dy;
                if (nx >= 0 && nx < row && ny >= 0 && ny < col && grid[nx][ny] === 1) {
                    if (nx === row - 1) {
                        found = true;
                        break;
                    }
                    queue.push([nx, ny]);
                    grid[nx][ny] = 0;
                }
            }
            if (found) break;
        }
        
        if (found) {
            ans = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return ans;
};

###Rust

use std::collections::VecDeque;

impl Solution {
    pub fn latest_day_to_cross(row: i32, col: i32, cells: Vec<Vec<i32>>) -> i32 {
        let dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)];
        let (row, col) = (row as usize, col as usize);
        
        let mut left = 0;
        let mut right = row * col;
        let mut ans = 0;
        
        while left <= right {
            let mid = (left + right) / 2;
            let mut grid = vec![vec![1; col]; row];
            for i in 0..mid {
                let r = (cells[i][0] - 1) as usize;
                let c = (cells[i][1] - 1) as usize;
                grid[r][c] = 0;
            }
            
            let mut queue = VecDeque::new();
            for i in 0..col {
                if grid[0][i] == 1 {
                    queue.push_back((0, i));
                    grid[0][i] = 0;
                }
            }
            
            let mut found = false;
            while let Some((x, y)) = queue.pop_front() {
                for (dx, dy) in &dirs {
                    let nx = x as i32 + dx;
                    let ny = y as i32 + dy;
                    
                    if nx >= 0 && nx < row as i32 && ny >= 0 && ny < col as i32 {
                        let (nx, ny) = (nx as usize, ny as usize);
                        if grid[nx][ny] == 1 {
                            if nx == row - 1 {
                                found = true;
                                break;
                            }
                            queue.push_back((nx, ny));
                            grid[nx][ny] = 0;
                        }
                    }
                }
                if found {
                    break;
                }
            }
            
            if found {
                ans = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        ans as i32
    }
}

复杂度分析

• 时间复杂度：$O(\textit{row} \times \textit{col} \times \log(\textit{row} \times \textit{col}))$。二分查找的次数为 $O(\log(\textit{row} \times \textit{col}))$，在二分查找的每一步中，我们需要 $O(\textit{row} \times \textit{col})$ 的时间进行广度优先搜索。

• 空间复杂度：$O(\textit{row} \times \textit{col})$，即为广度优先搜索中的矩阵以及队列需要使用的空间。

方法二：时光倒流 + 并查集

思路与算法

我们也可以倒着考虑这个问题：

在第 $\textit{row} \times \textit{col}$ 天时，矩阵中的每个格子都是水域。随后每往前推一天，就会有一个格子从水域变为陆地，问最少往前推几天可以从最上面一行走到最下面一行。

因此，我们可以将矩阵中的每一个格子看成并查集中的一个节点。当我们将 $(x, y)$ 从水域变为陆地时，我们将 $(x, y)$ 在并查集中的节点与上下左右四个方向的格子（如果对应的格子也是陆地）在并查集中的节点进行合并。

由于我们需要判断的是最上面一行与最下面一行的连通性，所以我们可以在并查集中额外添加两个超级节点 $s$ 和 $t$，分别表示最上面一行（整体）与最下面一行（整体）。如果 $(x, y)$ 中的 $x=0$，我们就将 $s$ 与 $(x, y)$ 在并查集中的节点进行合并；如果 $x=\textit{row}-1$，我们就将 $t$ 与 $(x, y)$ 在并查集中的节点进行合并。这样一来，只要 $(s, t)$ 在并查集中连通，就说明我们可以从最上面一行走到最下面一行。

代码

###C++

// 并查集模板
class UnionFind {
public:
    vector<int> parent;
    vector<int> size;
    int n;
    // 当前连通分量数目
    int setCount;
    
public:
    UnionFind(int _n): n(_n), setCount(_n), parent(_n), size(_n, 1) {
        iota(parent.begin(), parent.end(), 0);
    }
    
    int findset(int x) {
        return parent[x] == x ? x : parent[x] = findset(parent[x]);
    }
    
    bool unite(int x, int y) {
        x = findset(x);
        y = findset(y);
        if (x == y) {
            return false;
        }
        if (size[x] < size[y]) {
            swap(x, y);
        }
        parent[y] = x;
        size[x] += size[y];
        --setCount;
        return true;
    }
    
    bool connected(int x, int y) {
        x = findset(x);
        y = findset(y);
        return x == y;
    }
};

class Solution {
public:
    int latestDayToCross(int row, int col, vector<vector<int>>& cells) {
        // 编号为 n 的节点是超级节点 s
        // 编号为 n+1 的节点是超级节点 t
        int n = row * col;
        auto uf = UnionFind(n + 2);

        vector<vector<int>> valid(row, vector<int>(col));
        int ans = 0;
        for (int i = n - 1; i >= 0; --i) {
            int x = cells[i][0] - 1, y = cells[i][1] - 1;
            valid[x][y] = true;
            // 并查集是一维的，(x, y) 坐标是二维的，需要进行转换
            int id = x * col + y;
            if (x - 1 >= 0 && valid[x - 1][y]) {
                uf.unite(id, id - col);
            }
            if (x + 1 < row && valid[x + 1][y]) {
                uf.unite(id, id + col);
            }
            if (y - 1 >= 0 && valid[x][y - 1]) {
                uf.unite(id, id - 1);
            }
            if (y + 1 < col && valid[x][y + 1]) {
                uf.unite(id, id + 1);
            }
            if (x == 0) {
                uf.unite(id, n);
            }
            if (x == row - 1) {
                uf.unite(id, n + 1);
            }
            if (uf.connected(n, n + 1)) {
                ans = i;
                break;
            }
        }
        return ans;
    }
};

###Python

# 并查集模板
class UnionFind:
    def __init__(self, n: int):
        self.parent = list(range(n))
        self.size = [1] * n
        self.n = n
        # 当前连通分量数目
        self.setCount = n
    
    def findset(self, x: int) -> int:
        if self.parent[x] == x:
            return x
        self.parent[x] = self.findset(self.parent[x])
        return self.parent[x]
    
    def unite(self, x: int, y: int) -> bool:
        x, y = self.findset(x), self.findset(y)
        if x == y:
            return False
        if self.size[x] < self.size[y]:
            x, y = y, x
        self.parent[y] = x
        self.size[x] += self.size[y]
        self.setCount -= 1
        return True
    
    def connected(self, x: int, y: int) -> bool:
        x, y = self.findset(x), self.findset(y)
        return x == y

class Solution:
    def latestDayToCross(self, row: int, col: int, cells: List[List[int]]) -> int:
        # 编号为 n 的节点是超级节点 s
        # 编号为 n+1 的节点是超级节点 t
        n = row * col
        uf = UnionFind(n + 2)

        valid = [[0] * col for _ in range(row)]
        ans = 0
        for i in range(n - 1, -1, -1):
            x, y = cells[i][0] - 1, cells[i][1] - 1
            valid[x][y] = 1
            # 并查集是一维的，(x, y) 坐标是二维的，需要进行转换
            idx = x * col + y
            if x - 1 >= 0 and valid[x - 1][y]:
                uf.unite(idx, idx - col)
            if x + 1 < row and valid[x + 1][y]:
                uf.unite(idx, idx + col)
            if y - 1 >= 0 and valid[x][y - 1]:
                uf.unite(idx, idx - 1)
            if y + 1 < col and valid[x][y + 1]:
                uf.unite(idx, idx + 1)
            if x == 0:
                uf.unite(idx, n)
            if x == row - 1:
                uf.unite(idx, n + 1)
            if uf.connected(n, n + 1):
                ans = i
                break
        
        return ans

###Java

// 并查集模板
class UnionFind {
    public int[] parent;
    public int[] size;
    public int n;
    // 当前连通分量数目
    public int setCount;
    
    public UnionFind(int _n) {
        n = _n;
        setCount = _n;
        parent = new int[n];
        size = new int[n];
        Arrays.fill(size, 1);
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }
    
    public int findset(int x) {
        return parent[x] == x ? x : (parent[x] = findset(parent[x]));
    }
    
    public boolean unite(int x, int y) {
        x = findset(x);
        y = findset(y);
        if (x == y) {
            return false;
        }
        if (size[x] < size[y]) {
            int temp = x;
            x = y;
            y = temp;
        }
        parent[y] = x;
        size[x] += size[y];
        --setCount;
        return true;
    }
    
    public boolean connected(int x, int y) {
        return findset(x) == findset(y);
    }
}

class Solution {
    public int latestDayToCross(int row, int col, int[][] cells) {
        // 编号为 n 的节点是超级节点 s
        // 编号为 n+1 的节点是超级节点 t
        int n = row * col;
        UnionFind uf = new UnionFind(n + 2);
        int[][] valid = new int[row][col];
        int ans = 0;
        for (int i = n - 1; i >= 0; --i) {
            int x = cells[i][0] - 1, y = cells[i][1] - 1;
            valid[x][y] = 1;
            // 并查集是一维的，(x, y) 坐标是二维的，需要进行转换
            int id = x * col + y;
            if (x - 1 >= 0 && valid[x - 1][y] == 1) {
                uf.unite(id, id - col);
            }
            if (x + 1 < row && valid[x + 1][y] == 1) {
                uf.unite(id, id + col);
            }
            if (y - 1 >= 0 && valid[x][y - 1] == 1) {
                uf.unite(id, id - 1);
            }
            if (y + 1 < col && valid[x][y + 1] == 1) {
                uf.unite(id, id + 1);
            }
            if (x == 0) {
                uf.unite(id, n);
            }
            if (x == row - 1) {
                uf.unite(id, n + 1);
            }
            if (uf.connected(n, n + 1)) {
                ans = i;
                break;
            }
        }
        return ans;
    }
}

###C#

// 并查集模板
public class UnionFind {
    public int[] parent;
    public int[] size;
    public int n;
    // 当前连通分量数目
    public int setCount;
    
    public UnionFind(int _n) {
        n = _n;
        setCount = _n;
        parent = new int[n];
        size = new int[n];
        Array.Fill(size, 1);
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }
    
    public int findset(int x) {
        return parent[x] == x ? x : (parent[x] = findset(parent[x]));
    }
    
    public bool unite(int x, int y) {
        x = findset(x);
        y = findset(y);
        if (x == y) {
            return false;
        }
        if (size[x] < size[y]) {
            int temp = x;
            x = y;
            y = temp;
        }
        parent[y] = x;
        size[x] += size[y];
        --setCount;
        return true;
    }
    
    public bool connected(int x, int y) {
        return findset(x) == findset(y);
    }
}

public class Solution {
    public int LatestDayToCross(int row, int col, int[][] cells) {
        // 编号为 n 的节点是超级节点 s
        // 编号为 n+1 的节点是超级节点 t
        int n = row * col;
        UnionFind uf = new UnionFind(n + 2);
        int[][] valid = new int[row][];
        for (int i = 0; i < row; i++) {
            valid[i] = new int[col];
        }

        int ans = 0;
        for (int i = n - 1; i >= 0; --i) {
            int x = cells[i][0] - 1, y = cells[i][1] - 1;
            valid[x][y] = 1;
            // 并查集是一维的，(x, y) 坐标是二维的，需要进行转换
            int id = x * col + y;
            if (x - 1 >= 0 && valid[x - 1][y] == 1) {
                uf.unite(id, id - col);
            }
            if (x + 1 < row && valid[x + 1][y] == 1) {
                uf.unite(id, id + col);
            }
            if (y - 1 >= 0 && valid[x][y - 1] == 1) {
                uf.unite(id, id - 1);
            }
            if (y + 1 < col && valid[x][y + 1] == 1) {
                uf.unite(id, id + 1);
            }
            if (x == 0) {
                uf.unite(id, n);
            }
            if (x == row - 1) {
                uf.unite(id, n + 1);
            }
            if (uf.connected(n, n + 1)) {
                ans = i;
                break;
            }
        }
        
        return ans;
    }
}

###Go

func latestDayToCross(row int, col int, cells [][]int) int {
    // 编号为 n 的节点是超级节点 s
    // 编号为 n+1 的节点是超级节点 t
    n := row * col
    uf := newUnionFind(n + 2)
    valid := make([][]int, row)
    for i := range valid {
        valid[i] = make([]int, col)
    }
    ans := 0
    for i := n - 1; i >= 0; i-- {
        x, y := cells[i][0] - 1, cells[i][1] - 1
        valid[x][y] = 1
        // 并查集是一维的，(x, y) 坐标是二维的，需要进行转换
        id := x * col + y
        if x - 1 >= 0 && valid[x - 1][y] == 1 {
            uf.unite(id, id - col)
        }
        if x + 1 < row && valid[x + 1][y] == 1 {
            uf.unite(id, id + col)
        }
        if y - 1 >= 0 && valid[x][y - 1] == 1 {
            uf.unite(id, id - 1)
        }
        if y + 1 < col && valid[x][y + 1] == 1 {
            uf.unite(id, id + 1)
        }
        if x == 0 {
            uf.unite(id, n)
        }
        if x == row-1 {
            uf.unite(id, n + 1)
        }
        if uf.connected(n, n + 1) {
            ans = i
            break
        }
    }
    
    return ans
}

// 并查集模板
type UnionFind struct {
    parent []int
    size   []int
    n      int
    // 当前连通分量数目
    setCount int
}

func newUnionFind(n int) *UnionFind {
    parent := make([]int, n)
    size := make([]int, n)
    for i := range parent {
        parent[i] = i
        size[i] = 1
    }
    return &UnionFind{
        parent:   parent,
        size:     size,
        n:        n,
        setCount: n,
    }
}

func (uf *UnionFind) findset(x int) int {
    if uf.parent[x] != x {
        uf.parent[x] = uf.findset(uf.parent[x])
    }
    return uf.parent[x]
}

func (uf *UnionFind) unite(x, y int) bool {
    x, y = uf.findset(x), uf.findset(y)
    if x == y {
        return false
    }
    if uf.size[x] < uf.size[y] {
        x, y = y, x
    }
    uf.parent[y] = x
    uf.size[x] += uf.size[y]
    uf.setCount--
    return true
}

func (uf *UnionFind) connected(x, y int) bool {
    return uf.findset(x) == uf.findset(y)
}

###C

// 并查集模板
typedef struct {
    int* parent;
    int* size;
    int n;
    // 当前连通分量数目
    int setCount;
} UnionFind;

UnionFind* createUnionFind(int n) {
    UnionFind* uf = (UnionFind*)malloc(sizeof(UnionFind));
    uf->n = n;
    uf->setCount = n;
    uf->parent = (int*)malloc(n * sizeof(int));
    uf->size = (int*)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        uf->parent[i] = i;
        uf->size[i] = 1;
    }
    return uf;
}

int findset(UnionFind* uf, int x) {
    if (uf->parent[x] != x) {
        uf->parent[x] = findset(uf, uf->parent[x]);
    }
    return uf->parent[x];
}

int unite(UnionFind* uf, int x, int y) {
    x = findset(uf, x);
    y = findset(uf, y);
    if (x == y) {
        return 0;
    }
    if (uf->size[x] < uf->size[y]) {
        int temp = x;
        x = y;
        y = temp;
    }
    uf->parent[y] = x;
    uf->size[x] += uf->size[y];
    uf->setCount--;
    return 1;
}

int connected(UnionFind* uf, int x, int y) {
    return findset(uf, x) == findset(uf, y);
}

void freeUnionFind(UnionFind* uf) {
    free(uf->parent);
    free(uf->size);
    free(uf);
}

int latestDayToCross(int row, int col, int** cells, int cellsSize, int* cellsColSize) {
    // 编号为 n 的节点是超级节点 s
    // 编号为 n+1 的节点是超级节点 t
    int n = row * col;
    UnionFind* uf = createUnionFind(n + 2);
    int** valid = (int**)malloc(row * sizeof(int*));
    for (int i = 0; i < row; i++) {
        valid[i] = (int*)malloc(col * sizeof(int));
        memset(valid[i], 0, col * sizeof(int));
    }
    int ans = 0;
    for (int i = n - 1; i >= 0; --i) {
        int x = cells[i][0] - 1, y = cells[i][1] - 1;
        valid[x][y] = 1;
        // 并查集是一维的，(x, y) 坐标是二维的，需要进行转换
        int id = x * col + y;
        if (x - 1 >= 0 && valid[x - 1][y]) {
            unite(uf, id, id - col);
        }
        if (x + 1 < row && valid[x + 1][y]) {
            unite(uf, id, id + col);
        }
        if (y - 1 >= 0 && valid[x][y - 1]) {
            unite(uf, id, id - 1);
        }
        if (y + 1 < col && valid[x][y + 1]) {
            unite(uf, id, id + 1);
        }
        if (x == 0) {
            unite(uf, id, n);
        }
        if (x == row - 1) {
            unite(uf, id, n + 1);
        }
        if (connected(uf, n, n + 1)) {
            ans = i;
            break;
        }
    }
    
    // 释放内存
    for (int i = 0; i < row; i++) {
        free(valid[i]);
    }
    free(valid);
    freeUnionFind(uf);
    
    return ans;
}

###JavaScript

var latestDayToCross = function(row, col, cells) {
    // 编号为 n 的节点是超级节点 s
    // 编号为 n+1 的节点是超级节点 t
    const n = row * col;
    const uf = new UnionFind(n + 2);
    const valid = Array.from({length: row}, () => new Array(col).fill(0));
    let ans = 0;
    for (let i = n - 1; i >= 0; --i) {
        const x = cells[i][0] - 1, y = cells[i][1] - 1;
        valid[x][y] = 1;
        // 并查集是一维的，(x, y) 坐标是二维的，需要进行转换
        const id = x * col + y;
        if (x - 1 >= 0 && valid[x - 1][y] === 1) {
            uf.unite(id, id - col);
        }
        if (x + 1 < row && valid[x + 1][y] === 1) {
            uf.unite(id, id + col);
        }
        if (y - 1 >= 0 && valid[x][y - 1] === 1) {
            uf.unite(id, id - 1);
        }
        if (y + 1 < col && valid[x][y + 1] === 1) {
            uf.unite(id, id + 1);
        }
        if (x === 0) {
            uf.unite(id, n);
        }
        if (x === row - 1) {
            uf.unite(id, n + 1);
        }
        if (uf.connected(n, n + 1)) {
            ans = i;
            break;
        }
    }
    return ans;
}

// 并查集模板
class UnionFind {
    constructor(n) {
        this.parent = new Array(n);
        this.size = new Array(n).fill(1);
        this.n = n;
        // 当前连通分量数目
        this.setCount = n;
        for (let i = 0; i < n; i++) {
            this.parent[i] = i;
        }
    }
    
    findset(x) {
        return this.parent[x] === x ? x : (this.parent[x] = this.findset(this.parent[x]));
    }
    
    unite(x, y) {
        x = this.findset(x);
        y = this.findset(y);
        if (x === y) {
            return false;
        }
        if (this.size[x] < this.size[y]) {
            [x, y] = [y, x];
        }
        this.parent[y] = x;
        this.size[x] += this.size[y];
        this.setCount--;
        return true;
    }
    
    connected(x, y) {
        return this.findset(x) === this.findset(y);
    }
}

###TypeScript

function latestDayToCross(row: number, col: number, cells: number[][]): number {
    // 编号为 n 的节点是超级节点 s
    // 编号为 n+1 的节点是超级节点 t
    const n = row * col;
    const uf = new UnionFind(n + 2);
    const valid: number[][] = Array.from({length: row}, () => new Array(col).fill(0));
    let ans = 0;
    for (let i = n - 1; i >= 0; --i) {
        const x = cells[i][0] - 1, y = cells[i][1] - 1;
        valid[x][y] = 1;
        // 并查集是一维的，(x, y) 坐标是二维的，需要进行转换
        const id = x * col + y;
        if (x - 1 >= 0 && valid[x - 1][y] === 1) {
            uf.unite(id, id - col);
        }
        if (x + 1 < row && valid[x + 1][y] === 1) {
            uf.unite(id, id + col);
        }
        if (y - 1 >= 0 && valid[x][y - 1] === 1) {
            uf.unite(id, id - 1);
        }
        if (y + 1 < col && valid[x][y + 1] === 1) {
            uf.unite(id, id + 1);
        }
        if (x === 0) {
            uf.unite(id, n);
        }
        if (x === row - 1) {
            uf.unite(id, n + 1);
        }
        if (uf.connected(n, n + 1)) {
            ans = i;
            break;
        }
    }
    return ans;
};

// 并查集模板
class UnionFind {
    parent: number[];
    size: number[];
    n: number;
    // 当前连通分量数目
    setCount: number;
    
    constructor(n: number) {
        this.n = n;
        this.setCount = n;
        this.parent = new Array(n);
        this.size = new Array(n).fill(1);
        for (let i = 0; i < n; i++) {
            this.parent[i] = i;
        }
    }
    
    findset(x: number): number {
        return this.parent[x] === x ? x : (this.parent[x] = this.findset(this.parent[x]));
    }
    
    unite(x: number, y: number): boolean {
        x = this.findset(x);
        y = this.findset(y);
        if (x === y) {
            return false;
        }
        if (this.size[x] < this.size[y]) {
            [x, y] = [y, x];
        }
        this.parent[y] = x;
        this.size[x] += this.size[y];
        this.setCount--;
        return true;
    }
    
    connected(x: number, y: number): boolean {
        return this.findset(x) === this.findset(y);
    }
}

###Rust

// 并查集模板
struct UnionFind {
    parent: Vec<usize>,
    size: Vec<i32>,
    n: usize,
    // 当前连通分量数目
    set_count: i32,
}

impl UnionFind {
    fn new(n: usize) -> Self {
        let mut parent = vec![0; n];
        let size = vec![1; n];
        for i in 0..n {
            parent[i] = i;
        }
        UnionFind {
            parent,
            size,
            n,
            set_count: n as i32,
        }
    }
    
    fn findset(&mut self, x: usize) -> usize {
        if self.parent[x] != x {
            self.parent[x] = self.findset(self.parent[x]);
        }
        self.parent[x]
    }
    
    fn unite(&mut self, x: usize, y: usize) -> bool {
        let mut x = self.findset(x);
        let mut y = self.findset(y);
        if x == y {
            return false;
        }
        if self.size[x] < self.size[y] {
            std::mem::swap(&mut x, &mut y);
        }
        self.parent[y] = x;
        self.size[x] += self.size[y];
        self.set_count -= 1;
        true
    }
    
    fn connected(&mut self, x: usize, y: usize) -> bool {
        self.findset(x) == self.findset(y)
    }
}

impl Solution {
    pub fn latest_day_to_cross(row: i32, col: i32, cells: Vec<Vec<i32>>) -> i32 {
        // 编号为 n 的节点是超级节点 s
        // 编号为 n+1 的节点是超级节点 t
        let (row, col) = (row as usize, col as usize);
        let n = row * col;
        let mut uf = UnionFind::new(n + 2);
        let mut valid = vec![vec![0; col]; row];
        let mut ans = 0;
        for i in (0..n).rev() {
            let x = (cells[i][0] - 1) as usize;
            let y = (cells[i][1] - 1) as usize;
            valid[x][y] = 1;
            // 并查集是一维的，(x, y) 坐标是二维的，需要进行转换
            let id = x * col + y;
            if x > 0 && valid[x - 1][y] == 1 {
                uf.unite(id, id - col);
            }
            if x + 1 < row && valid[x + 1][y] == 1 {
                uf.unite(id, id + col);
            }
            if y > 0 && valid[x][y - 1] == 1 {
                uf.unite(id, id - 1);
            }
            if y + 1 < col && valid[x][y + 1] == 1 {
                uf.unite(id, id + 1);
            }
            if x == 0 {
                uf.unite(id, n);
            }
            if x == row - 1 {
                uf.unite(id, n + 1);
            }
            if uf.connected(n, n + 1) {
                ans = i;
                break;
            }
        }
        ans as i32
    }
}

复杂度分析

• 时间复杂度：$O(\textit{row} \times \textit{col} \times \alpha(\textit{row} \times \textit{col}))$。其中 $\alpha$ 是阿克曼函数的反函数，表示并查集在均摊意义下单次操作需要的时间。

• 空间复杂度：$O(\textit{row} \times \textit{col})$，即为并查集需要的空间。

方法一：逆序（时光倒流）

写法一：并查集

本质是判断最上边和最下边是否连通。

可以用并查集判断是否连通。并查集加边很好做，但删边不好做。

如果时光倒流，删边就成了加边（把水变成陆地）。

代码实现时，可以把格子 $(r,c)$ 映射为 $rn + c$，并创建两个虚拟节点 $mn$ 和 $mn+1$，分别表示最上边（第一行的上面）和最下边（最后一行的下面），方便我们判断最上边和最下边是否连通。

• 如果 $(r,c)$ 从水变成陆地，那么把 $(r,c)$ 和上下左右的陆地格子连起来（注意不要把陆地和水连起来）。
• 特别地，如果 $(r,c)$ 上面没有格子，那么和 $mn$ 相连。
• 特别地，如果 $(r,c)$ 下面没有格子，那么和 $mn+1$ 相连。

最上边和最下边是否连通，等价于判断节点 $mn$ 和 $mn+1$ 是否连通。

倒着遍历 $\textit{cells}$，一旦发现连通就立刻返回答案。

注意题目保证 $\textit{cells}$ 的长度等于 $mn$，第 $0$ 天一定连通，第 $mn-1$ 天一定不连通。

关于并查集的完整模板，见 数据结构题单。

class UnionFind:
    def __init__(self, n: int):
        # 一开始有 n 个集合 {0}, {1}, ..., {n-1}
        # 集合 i 的代表元是自己
        self._fa = list(range(n))  # 代表元

    # 返回 x 所在集合的代表元
    # 同时做路径压缩，也就是把 x 所在集合中的所有元素的 fa 都改成代表元
    def find(self, x: int) -> int:
        fa = self._fa
        # 如果 fa[x] == x，则表示 x 是代表元
        if fa[x] != x:
            fa[x] = self.find(fa[x])  # fa 改成代表元
        return fa[x]

    # 判断 x 和 y 是否在同一个集合
    def is_same(self, x: int, y: int) -> bool:
        # 如果 x 的代表元和 y 的代表元相同，那么 x 和 y 就在同一个集合
        # 这就是代表元的作用：用来快速判断两个元素是否在同一个集合
        return self.find(x) == self.find(y)

    # 把 from 所在集合合并到 to 所在集合中
    def merge(self, from_: int, to: int) -> None:
        x, y = self.find(from_), self.find(to)
        self._fa[x] = y  # 合并集合。修改后就可以认为 from 和 to 在同一个集合了


class Solution:
    def latestDayToCross(self, m: int, n: int, cells: List[List[int]]) -> int:
        DIRS = (0, -1), (0, 1), (-1, 0), (1, 0)  # 左右上下

        top = m * n
        bottom = m * n + 1
        uf = UnionFind(m * n + 2)
        land = [[False] * n for _ in range(m)]

        for day in range(len(cells) - 1, -1, -1):
            r, c = cells[day]
            r -= 1  # 改成从 0 开始的下标
            c -= 1
            v = r * n + c
            land[r][c] = True  # 变成陆地

            if r == 0:
                uf.merge(v, top)  # 与最上边相连

            if r == m - 1:
                uf.merge(v, bottom)  # 与最下边相连

            for dx, dy in DIRS:
                x, y = r + dx, c + dy
                if 0 <= x < m and 0 <= y < n and land[x][y]:
                    uf.merge(v, x * n + y)  # 与四周的陆地相连

            if uf.is_same(top, bottom):  # 最上边和最下边连通
                return day

class UnionFind {
    private final int[] fa; // 代表元

    UnionFind(int n) {
        // 一开始有 n 个集合 {0}, {1}, ..., {n-1}
        // 集合 i 的代表元是自己
        fa = new int[n];
        for (int i = 0; i < n; i++) {
            fa[i] = i;
        }
    }

    // 返回 x 所在集合的代表元
    // 同时做路径压缩，也就是把 x 所在集合中的所有元素的 fa 都改成代表元
    public int find(int x) {
        // 如果 fa[x] == x，则表示 x 是代表元
        if (fa[x] != x) {
            fa[x] = find(fa[x]); // fa 改成代表元
        }
        return fa[x];
    }

    // 判断 x 和 y 是否在同一个集合
    public boolean isSame(int x, int y) {
        // 如果 x 的代表元和 y 的代表元相同，那么 x 和 y 就在同一个集合
        // 这就是代表元的作用：用来快速判断两个元素是否在同一个集合
        return find(x) == find(y);
    }

    // 把 from 所在集合合并到 to 所在集合中
    public void merge(int from, int to) {
        int x = find(from);
        int y = find(to);
        fa[x] = y; // 合并集合。修改后就可以认为 from 和 to 在同一个集合了
    }
}

class Solution {
    private static final int[][] DIRS = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}}; // 左右上下

    public int latestDayToCross(int m, int n, int[][] cells) {
        int top = m * n;
        int bottom = m * n + 1;
        UnionFind uf = new UnionFind(m * n + 2);
        boolean[][] land = new boolean[m][n];

        for (int day = cells.length - 1; ; day--) {
            int[] cell = cells[day];
            int r = cell[0] - 1; // 改成从 0 开始的下标
            int c = cell[1] - 1;
            int v = r * n + c;
            land[r][c] = true; // 变成陆地

            if (r == 0) {
                uf.merge(v, top); // 与最上边相连
            }

            if (r == m - 1) {
                uf.merge(v, bottom); // 与最下边相连
            }

            for (int[] d : DIRS) {
                int x = r + d[0];
                int y = c + d[1];
                if (0 <= x && x < m && 0 <= y && y < n && land[x][y]) {
                    uf.merge(v, x * n + y); // 与四周的陆地相连
                }
            }

            if (uf.isSame(top, bottom)) { // 最上边和最下边连通
                return day;
            }
        }
    }
}

class UnionFind {
    vector<int> fa; // 代表元

public:
    UnionFind(int n) : fa(n) {
        // 一开始有 n 个集合 {0}, {1}, ..., {n-1}
        // 集合 i 的代表元是自己
        ranges::iota(fa, 0); // iota(fa.begin(), fa.end(), 0);
    }

    // 返回 x 所在集合的代表元
    // 同时做路径压缩，也就是把 x 所在集合中的所有元素的 fa 都改成代表元
    int find(int x) {
        // 如果 fa[x] == x，则表示 x 是代表元
        if (fa[x] != x) {
            fa[x] = find(fa[x]); // fa 改成代表元
        }
        return fa[x];
    }

    // 判断 x 和 y 是否在同一个集合
    bool is_same(int x, int y) {
        // 如果 x 的代表元和 y 的代表元相同，那么 x 和 y 就在同一个集合
        // 这就是代表元的作用：用来快速判断两个元素是否在同一个集合
        return find(x) == find(y);
    }

    // 把 from 所在集合合并到 to 所在集合中
    void merge(int from, int to) {
        int x = find(from), y = find(to);
        fa[x] = y; // 合并集合。修改后就可以认为 from 和 to 在同一个集合了
    }
};

class Solution {
    static constexpr int DIRS[4][2] = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}}; // 左右上下

public:
    int latestDayToCross(int m, int n, vector<vector<int>>& cells) {
        int top = m * n;
        int bottom = m * n + 1;
        UnionFind uf(m * n + 2);
        vector land(m, vector<int8_t>(n));

        for (int day = cells.size() - 1; ; day--) {
            auto& cell = cells[day];
            int r = cell[0] - 1; // 改成从 0 开始的下标
            int c = cell[1] - 1;
            int v = r * n + c;
            land[r][c] = true; // 变成陆地

            if (r == 0) {
                uf.merge(v, top); // 与最上边相连
            }

            if (r == m - 1) {
                uf.merge(v, bottom); // 与最下边相连
            }

            for (auto& d : DIRS) {
                int x = r + d[0], y = c + d[1];
                if (0 <= x && x < m && 0 <= y && y < n && land[x][y]) {
                    uf.merge(v, x * n + y); // 与四周的陆地相连
                }
            }

            if (uf.is_same(top, bottom)) { // 最上边和最下边连通
                return day;
            }
        }
    }
};

type unionFind struct {
fa []int // 代表元
}

func newUnionFind(n int) unionFind {
fa := make([]int, n)
// 一开始有 n 个集合 {0}, {1}, ..., {n-1}
// 集合 i 的代表元是自己
for i := range fa {
fa[i] = i
}
return unionFind{fa}
}

// 返回 x 所在集合的代表元
// 同时做路径压缩，也就是把 x 所在集合中的所有元素的 fa 都改成代表元
func (u unionFind) find(x int) int {
// 如果 fa[x] == x，则表示 x 是代表元
if u.fa[x] != x {
u.fa[x] = u.find(u.fa[x]) // fa 改成代表元
}
return u.fa[x]
}

// 判断 x 和 y 是否在同一个集合
func (u unionFind) same(x, y int) bool {
// 如果 x 的代表元和 y 的代表元相同，那么 x 和 y 就在同一个集合
// 这就是代表元的作用：用来快速判断两个元素是否在同一个集合
return u.find(x) == u.find(y)
}

// 把 from 所在集合合并到 to 所在集合中
func (u *unionFind) merge(from, to int) {
x, y := u.find(from), u.find(to)
u.fa[x] = y // 合并集合。修改后就可以认为 from 和 to 在同一个集合了
}

var dirs = []struct{ x, y int }{{0, -1}, {0, 1}, {-1, 0}, {1, 0}} // 左右上下

func latestDayToCross(m, n int, cells [][]int) int {
top := m * n
bottom := m*n + 1
uf := newUnionFind(m*n + 2)

land := make([][]bool, m)
for i := range land {
land[i] = make([]bool, n)
}

for day := len(cells) - 1; ; day-- {
cell := cells[day]
r, c := cell[0]-1, cell[1]-1 // 改成从 0 开始的下标
v := r*n + c
land[r][c] = true // 变成陆地

if r == 0 {
uf.merge(v, top) // 与最上边相连
}

if r == m-1 {
uf.merge(v, bottom) // 与最下边相连
}

for _, d := range dirs {
x, y := r+d.x, c+d.y
if 0 <= x && x < m && 0 <= y && y < n && land[x][y] {
uf.merge(v, x*n+y) // 与四周的陆地相连
}
}

if uf.same(top, bottom) { // 最上边和最下边连通
return day
}
}
}

复杂度分析

• 时间复杂度：$\mathcal{O}(mn\log(mn))$。
• 空间复杂度：$\mathcal{O}(mn)$。

写法二：DFS

想象最上边有病毒，要感染到最下边。

在倒着遍历 $\textit{cells}$，把水变成陆地的过程中：

• 如果陆地在第一行，那么被感染。
• 如果陆地上下左右是水，或者未被感染的陆地，那么这个陆地未被感染。
• 如果陆地与被感染的陆地相邻，那么也被感染。⚠注意：如果 $(r,c)$ 从水变成陆地后，把被感染的陆地与未被感染的陆地连起来，那么我们还需要从 $(r,c)$ 出发，DFS 访问其余未被感染的陆地，把访问到的陆地也标记为被感染。

class Solution:
    def latestDayToCross(self, m: int, n: int, cells: List[List[int]]) -> int:
        DIRS = (0, -1), (0, 1), (-1, 0), (1, 0)  # 左右上下

        # 0：水
        # 1：陆地（未被感染）
        # 2：陆地（已被感染）
        state = [[0] * n for _ in range(m)]

        # 能否从第一行到达 (r, c)
        def can_reach_from_top(r: int, c: int) -> bool:
            if r == 0:  # 已经是第一行
                return True
            for dx, dy in DIRS:
                x, y = r + dx, c + dy
                if 0 <= x < m and 0 <= y < n and state[x][y] == 2:
                    return True
            return False

        # 从 (r, c) 出发，能否到达最后一行
        def dfs(r: int, c: int) -> bool:
            if r == m - 1:
                return True
            state[r][c] = 2  # 感染
            for dx, dy in DIRS:
                x, y = r + dx, c + dy
                # 传播病毒到未被感染的陆地
                if 0 <= x < m and 0 <= y < n and state[x][y] == 1 and dfs(x, y):
                    return True
            return False

        for day in range(len(cells) - 1, -1, -1):
            r, c = cells[day]
            r -= 1  # 改成从 0 开始的下标
            c -= 1
            state[r][c] = 1  # 未被感染的陆地
            if can_reach_from_top(r, c) and dfs(r, c):
                return day

class Solution {
    private static final int[][] DIRS = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}}; // 左右上下

    public int latestDayToCross(int m, int n, int[][] cells) {
        // 0：水
        // 1：陆地（未被感染）
        // 2：陆地（已被感染）
        byte[][] state = new byte[m][n];

        for (int day = cells.length - 1; ; day--) {
            int[] cell = cells[day];
            int r = cell[0] - 1; // 改成从 0 开始的下标
            int c = cell[1] - 1;
            state[r][c] = 1; // 未被感染的陆地
            if (canReachFromTop(r, c, state) && dfs(r, c, state)) {
                return day;
            }
        }
    }

    // 能否从第一行到达 (r, c)
    private boolean canReachFromTop(int r, int c, byte[][] state) {
        if (r == 0) { // 已经是第一行
            return true;
        }
        for (int[] d : DIRS) {
            int x = r + d[0];
            int y = c + d[1];
            if (0 <= x && x < state.length && 0 <= y && y < state[x].length && state[x][y] == 2) {
                return true;
            }
        }
        return false;
    }

    // 从 (r, c) 出发，能否到达最后一行
    private boolean dfs(int r, int c, byte[][] state) {
        int m = state.length;
        if (r == m - 1) {
            return true;
        }
        state[r][c] = 2; // 感染
        for (int[] d : DIRS) {
            int x = r + d[0];
            int y = c + d[1];
            // 传播病毒到未被感染的陆地
            if (0 <= x && x < m && 0 <= y && y < state[x].length && state[x][y] == 1 && dfs(x, y, state)) {
                return true;
            }
        }
        return false;
    }
}

class Solution {
    static constexpr int DIRS[4][2] = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}}; // 左右上下

public:
    int latestDayToCross(int m, int n, vector<vector<int>>& cells) {
        // 0：水
        // 1：陆地（未被感染）
        // 2：陆地（已被感染）
        vector state(m, vector<int8_t>(n));

        auto can_reach_from_top = [&](int r, int c) -> bool {
            if (r == 0) { // 已经是第一行
                return true;
            }
            for (auto& d : DIRS) {
                int x = r + d[0], y = c + d[1];
                if (0 <= x && x < m && 0 <= y && y < n && state[x][y] == 2) {
                    return true;
                }
            }
            return false;
        };

        auto dfs = [&](this auto&& dfs, int r, int c) -> bool {
            if (r == m - 1) {
                return true;
            }
            state[r][c] = 2; // 感染
            for (auto& d : DIRS) {
                int x = r + d[0], y = c + d[1];
                // 传播病毒到未被感染的陆地
                if (0 <= x && x < m && 0 <= y && y < n && state[x][y] == 1 && dfs(x, y)) {
                    return true;
                }
            }
            return false;
        };

        for (int day = cells.size() - 1; ; day--) {
            auto& cell = cells[day];
            int r = cell[0] - 1; // 改成从 0 开始的下标
            int c = cell[1] - 1;
            state[r][c] = 1; // 未被感染的陆地
            if (can_reach_from_top(r, c) && dfs(r, c)) {
                return day;
            }
        }
    }
};

var dirs = []struct{ x, y int }{{0, -1}, {0, 1}, {-1, 0}, {1, 0}} // 左右上下

func latestDayToCross(m, n int, cells [][]int) int {
// 0：水
// 1：陆地（未被感染）
// 2：陆地（已被感染）
state := make([][]int8, m)
for i := range state {
state[i] = make([]int8, n)
}

// 能否从第一行到达 (r, c)
canReachFromTop := func(r, c int) bool {
if r == 0 { // 已经是第一行
return true
}
for _, d := range dirs {
x, y := r+d.x, c+d.y
if 0 <= x && x < m && 0 <= y && y < n && state[x][y] == 2 {
return true
}
}
return false
}

// 从 (r, c) 出发，能否到达最后一行
var dfs func(int, int) bool
dfs = func(r, c int) bool {
if r == m-1 {
return true
}
state[r][c] = 2 // 感染
for _, d := range dirs {
x, y := r+d.x, c+d.y
// 传播病毒到未被感染的陆地
if 0 <= x && x < m && 0 <= y && y < n && state[x][y] == 1 && dfs(x, y) {
return true
}
}
return false
}

for day := len(cells) - 1; ; day-- {
cell := cells[day]
r, c := cell[0]-1, cell[1]-1 // 改成从 0 开始的下标
state[r][c] = 1 // 未被感染的陆地
if canReachFromTop(r, c) && dfs(r, c) {
return day
}
}
}

复杂度分析

• 时间复杂度：$\mathcal{O}(mn)$。在 DFS 中，同一个格子至多访问（被感染）一次。
• 空间复杂度：$\mathcal{O}(mn)$。

方法二：正序

也可以正序遍历 $\textit{cells}$。

把网格图视作一块木板，把水视作被腐蚀掉的木板。

什么时候木板断开，即没有任何从上到下的完整段，那么前一天就是答案。

这等价于水可以从最左边流到最右边，注意水可以向八个方向移动（见上图最后一天）。

写法一：并查集

把格子 $(r,c)$ 映射为 $rn + c$，并创建两个虚拟节点 $mn$ 和 $mn+1$，分别表示最左边（第一列的左边）和最右边（最后一列的右边），方便我们判断最左边和最右边是否连通。

• 如果 $(r,c)$ 从陆地变成水，那么把 $(r,c)$ 和八个方向的水格子连起来。
• 特别地，如果 $(r,c)$ 左边没有格子，那么和 $mn$ 相连。
• 特别地，如果 $(r,c)$ 右边没有格子，那么和 $mn+1$ 相连。

最左边和最右边是否连通，等价于判断节点 $mn$ 和 $mn+1$ 是否连通。

class UnionFind:
    def __init__(self, n: int):
        # 一开始有 n 个集合 {0}, {1}, ..., {n-1}
        # 集合 i 的代表元是自己
        self._fa = list(range(n))  # 代表元

    # 返回 x 所在集合的代表元
    # 同时做路径压缩，也就是把 x 所在集合中的所有元素的 fa 都改成代表元
    def find(self, x: int) -> int:
        fa = self._fa
        # 如果 fa[x] == x，则表示 x 是代表元
        if fa[x] != x:
            fa[x] = self.find(fa[x])  # fa 改成代表元
        return fa[x]

    # 判断 x 和 y 是否在同一个集合
    def is_same(self, x: int, y: int) -> bool:
        # 如果 x 的代表元和 y 的代表元相同，那么 x 和 y 就在同一个集合
        # 这就是代表元的作用：用来快速判断两个元素是否在同一个集合
        return self.find(x) == self.find(y)

    # 把 from 所在集合合并到 to 所在集合中
    def merge(self, from_: int, to: int) -> None:
        x, y = self.find(from_), self.find(to)
        self._fa[x] = y  # 合并集合。修改后就可以认为 from 和 to 在同一个集合了


class Solution:
    def latestDayToCross(self, m: int, n: int, cells: List[List[int]]) -> int:
        DIRS = (-1, -1), (-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1)

        left = m * n
        right = m * n + 1
        uf = UnionFind(m * n + 2)
        water = [[False] * n for _ in range(m)]

        for day, (r, c) in enumerate(cells):
            r -= 1  # 改成从 0 开始的下标
            c -= 1
            v = r * n + c
            water[r][c] = True  # 变成水

            if c == 0:
                uf.merge(v, left)  # 与最左边相连

            if c == n - 1:
                uf.merge(v, right)  # 与最右边相连

            for dx, dy in DIRS:
                x, y = r + dx, c + dy
                if 0 <= x < m and 0 <= y < n and water[x][y]:
                    uf.merge(v, x * n + y)  # 与八方向的水相连

            if uf.is_same(left, right):  # 最左边和最右边连通
                return day

class UnionFind {
    private final int[] fa; // 代表元

    UnionFind(int n) {
        // 一开始有 n 个集合 {0}, {1}, ..., {n-1}
        // 集合 i 的代表元是自己
        fa = new int[n];
        for (int i = 0; i < n; i++) {
            fa[i] = i;
        }
    }

    // 返回 x 所在集合的代表元
    // 同时做路径压缩，也就是把 x 所在集合中的所有元素的 fa 都改成代表元
    public int find(int x) {
        // 如果 fa[x] == x，则表示 x 是代表元
        if (fa[x] != x) {
            fa[x] = find(fa[x]); // fa 改成代表元
        }
        return fa[x];
    }

    // 判断 x 和 y 是否在同一个集合
    public boolean isSame(int x, int y) {
        // 如果 x 的代表元和 y 的代表元相同，那么 x 和 y 就在同一个集合
        // 这就是代表元的作用：用来快速判断两个元素是否在同一个集合
        return find(x) == find(y);
    }

    // 把 from 所在集合合并到 to 所在集合中
    public void merge(int from, int to) {
        int x = find(from);
        int y = find(to);
        fa[x] = y; // 合并集合。修改后就可以认为 from 和 to 在同一个集合了
    }
}

class Solution {
    private static final int[][] DIRS = {{-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}};

    public int latestDayToCross(int m, int n, int[][] cells) {
        int left = m * n;
        int right = m * n + 1;
        UnionFind uf = new UnionFind(m * n + 2);
        boolean[][] water = new boolean[m][n];

        for (int day = 0; ; day++) {
            int[] cell = cells[day];
            int r = cell[0] - 1; // 改成从 0 开始的下标
            int c = cell[1] - 1;
            int v = r * n + c;
            water[r][c] = true; // 变成水

            if (c == 0) {
                uf.merge(v, left); // 与最左边相连
            }

            if (c == n - 1) {
                uf.merge(v, right); // 与最右边相连
            }

            for (int[] d : DIRS) {
                int x = r + d[0];
                int y = c + d[1];
                if (0 <= x && x < m && 0 <= y && y < n && water[x][y]) {
                    uf.merge(v, x * n + y); // 与八方向的水相连
                }
            }

            if (uf.isSame(left, right)) { // 最左边和最右边连通
                return day;
            }
        }
    }
}

class UnionFind {
    vector<int> fa; // 代表元

public:
    UnionFind(int n) : fa(n) {
        // 一开始有 n 个集合 {0}, {1}, ..., {n-1}
        // 集合 i 的代表元是自己
        ranges::iota(fa, 0); // iota(fa.begin(), fa.end(), 0);
    }

    // 返回 x 所在集合的代表元
    // 同时做路径压缩，也就是把 x 所在集合中的所有元素的 fa 都改成代表元
    int find(int x) {
        // 如果 fa[x] == x，则表示 x 是代表元
        if (fa[x] != x) {
            fa[x] = find(fa[x]); // fa 改成代表元
        }
        return fa[x];
    }

    // 判断 x 和 y 是否在同一个集合
    bool is_same(int x, int y) {
        // 如果 x 的代表元和 y 的代表元相同，那么 x 和 y 就在同一个集合
        // 这就是代表元的作用：用来快速判断两个元素是否在同一个集合
        return find(x) == find(y);
    }

    // 把 from 所在集合合并到 to 所在集合中
    void merge(int from, int to) {
        int x = find(from), y = find(to);
        fa[x] = y; // 合并集合。修改后就可以认为 from 和 to 在同一个集合了
    }
};

class Solution {
    static constexpr int DIRS[8][2] = {{-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}};

public:
    int latestDayToCross(int m, int n, vector<vector<int>>& cells) {
        int left = m * n;
        int right = m * n + 1;
        UnionFind uf(m * n + 2);
        vector water(m, vector<int8_t>(n));

        for (int day = 0; ; day++) {
            auto& cell = cells[day];
            int r = cell[0] - 1; // 改成从 0 开始的下标
            int c = cell[1] - 1;
            int v = r * n + c;
            water[r][c] = true; // 变成水

            if (c == 0) {
                uf.merge(v, left); // 与最左边相连
            }

            if (c == n - 1) {
                uf.merge(v, right); // 与最右边相连
            }

            for (auto& d : DIRS) {
                int x = r + d[0], y = c + d[1];
                if (0 <= x && x < m && 0 <= y && y < n && water[x][y]) {
                    uf.merge(v, x * n + y); // 与八方向的水相连
                }
            }

            if (uf.is_same(left, right)) { // 最左边和最右边连通
                return day;
            }
        }
    }
};

type unionFind struct {
fa []int // 代表元
}

func newUnionFind(n int) unionFind {
fa := make([]int, n)
// 一开始有 n 个集合 {0}, {1}, ..., {n-1}
// 集合 i 的代表元是自己
for i := range fa {
fa[i] = i
}
return unionFind{fa}
}

// 返回 x 所在集合的代表元
// 同时做路径压缩，也就是把 x 所在集合中的所有元素的 fa 都改成代表元
func (u unionFind) find(x int) int {
// 如果 fa[x] == x，则表示 x 是代表元
if u.fa[x] != x {
u.fa[x] = u.find(u.fa[x]) // fa 改成代表元
}
return u.fa[x]
}

// 判断 x 和 y 是否在同一个集合
func (u unionFind) same(x, y int) bool {
// 如果 x 的代表元和 y 的代表元相同，那么 x 和 y 就在同一个集合
// 这就是代表元的作用：用来快速判断两个元素是否在同一个集合
return u.find(x) == u.find(y)
}

// 把 from 所在集合合并到 to 所在集合中
func (u *unionFind) merge(from, to int) {
x, y := u.find(from), u.find(to)
u.fa[x] = y // 合并集合。修改后就可以认为 from 和 to 在同一个集合了
}

var dirs = []struct{ x, y int }{{-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}}

func latestDayToCross(m, n int, cells [][]int) int {
left := m * n
right := m*n + 1
uf := newUnionFind(m*n + 2)

water := make([][]bool, m)
for i := range water {
water[i] = make([]bool, n)
}

for day, cell := range cells {
r, c := cell[0]-1, cell[1]-1 // 改成从 0 开始的下标
v := r*n + c
water[r][c] = true // 变成水

if c == 0 {
uf.merge(v, left) // 与最左边相连
}

if c == n-1 {
uf.merge(v, right) // 与最右边相连
}

for _, d := range dirs {
x, y := r+d.x, c+d.y
if 0 <= x && x < m && 0 <= y && y < n && water[x][y] {
uf.merge(v, x*n+y) // 与八方向的水相连
}
}

if uf.same(left, right) { // 最左边和最右边连通
return day
}
}
return -1
}

复杂度分析

• 时间复杂度：$\mathcal{O}(mn\log(mn))$。
• 空间复杂度：$\mathcal{O}(mn)$。

写法二：DFS

思路同方法一的 DFS。

class Solution:
    def latestDayToCross(self, m: int, n: int, cells: List[List[int]]) -> int:
        DIRS = (-1, -1), (-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1)

        # 0：陆地
        # 1：水（未被感染）
        # 2：水（已被感染）
        state = [[0] * n for _ in range(m)]

        def can_reach_from_left(r: int, c: int) -> bool:
            if c == 0:  # 已经是第一列
                return True
            for dx, dy in DIRS:
                x, y = r + dx, c + dy
                if 0 <= x < m and 0 <= y < n and state[x][y] == 2:
                    return True
            return False

        def dfs(r: int, c: int) -> bool:
            if c == n - 1:
                return True
            state[r][c] = 2  # 感染
            for dx, dy in DIRS:
                x, y = r + dx, c + dy
                if 0 <= x < m and 0 <= y < n and state[x][y] == 1 and dfs(x, y):
                    return True
            return False

        for day, (r, c) in enumerate(cells):
            r -= 1  # 改成从 0 开始的下标
            c -= 1
            state[r][c] = 1  # 未被感染的水
            if can_reach_from_left(r, c) and dfs(r, c):
                return day

class Solution {
    private static final int[][] DIRS = {{-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}};

    // 能否从第一列到达 (r, c)
    private boolean canReachFromLeft(int r, int c, byte[][] state) {
        if (c == 0) { // 已经是第一列
            return true;
        }
        for (int[] d : DIRS) {
            int x = r + d[0];
            int y = c + d[1];
            if (0 <= x && x < state.length && 0 <= y && y < state[x].length && state[x][y] == 2) {
                return true;
            }
        }
        return false;
    }

    // 从 (r, c) 出发，能否到达最后一列
    private boolean dfs(int r, int c, byte[][] state) {
        int n = state[0].length;
        if (c == n - 1) {
            return true;
        }
        state[r][c] = 2; // 感染
        for (int[] d : DIRS) {
            int x = r + d[0];
            int y = c + d[1];
            if (0 <= x && x < state.length && 0 <= y && y < n && state[x][y] == 1 && dfs(x, y, state)) {
                return true;
            }
        }
        return false;
    }

    public int latestDayToCross(int m, int n, int[][] cells) {
        // 0：陆地
        // 1：水（未被感染）
        // 2：水（已被感染）
        byte[][] state = new byte[m][n];

        for (int day = 0; ; day++) {
            int[] cell = cells[day];
            int r = cell[0] - 1; // 改成从 0 开始的下标
            int c = cell[1] - 1;
            state[r][c] = 1; // 未被感染的水
            if (canReachFromLeft(r, c, state) && dfs(r, c, state)) {
                return day;
            }
        }
    }
}

class Solution {
    static constexpr int DIRS[8][2] = {{-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}};

public:
    int latestDayToCross(int m, int n, vector<vector<int>>& cells) {
        // 0：陆地
        // 1：水（未被感染）
        // 2：水（已被感染）
        vector state(m, vector<int8_t>(n));

        auto can_reach_from_left = [&](int r, int c) {
            if (c == 0) {
                return true;
            }
            for (auto& d : DIRS) {
                int x = r + d[0], y = c + d[1];
                if (0 <= x && x < m && 0 <= y && y < n && state[x][y] == 2) {
                    return true;
                }
            }
            return false;
        };

        auto dfs = [&](this auto&& dfs, int r, int c) -> bool {
            if (c == n - 1) {
                return true;
            }
            state[r][c] = 2; // 感染
            for (auto& d : DIRS) {
                int x = r + d[0], y = c + d[1];
                if (0 <= x && x < m && 0 <= y && y < n && state[x][y] == 1 && dfs(x, y)) {
                    return true;
                }
            }
            return false;
        };

        for (int day = 0; ; day++) {
            auto& cell = cells[day];
            int r = cell[0] - 1; // 改成从 0 开始的下标
            int c = cell[1] - 1;
            state[r][c] = 1; // 未被感染的水
            if (can_reach_from_left(r, c) && dfs(r, c)) {
                return day;
            }
        }
    }
};

var dirs = []struct{ x, y int }{{-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}}

func latestDayToCross(m, n int, cells [][]int) int {
// 0：陆地
// 1：水（未被感染）
// 2：水（已被感染）
state := make([][]int8, m)
for i := range state {
state[i] = make([]int8, n)
}

// 能否从第一列到达 (r, c)
canReachFromLeft := func(r, c int) bool {
if c == 0 { // 已经是第一列
return true
}
for _, d := range dirs {
x, y := r+d.x, c+d.y
if 0 <= x && x < m && 0 <= y && y < n && state[x][y] == 2 {
return true
}
}
return false
}

// 从 (r, c) 出发，能否到达最后一列
var dfs func(int, int) bool
dfs = func(r, c int) bool {
if c == n-1 {
return true
}
state[r][c] = 2 // 感染
for _, d := range dirs {
x, y := r+d.x, c+d.y
// 传播病毒到未被感染的水
if 0 <= x && x < m && 0 <= y && y < n && state[x][y] == 1 && dfs(x, y) {
return true
}
}
return false
}

for day, cell := range cells {
r, c := cell[0]-1, cell[1]-1 // 改成从 0 开始的下标
state[r][c] = 1 // 未被感染的水
if canReachFromLeft(r, c) && dfs(r, c) {
return day
}
}
return -1
}

复杂度分析

• 时间复杂度：$\mathcal{O}(mn)$。
• 空间复杂度：$\mathcal{O}(mn)$。

相似题目

803. 打砖块

专题训练

见下面思维题单的「§5.3 逆向思维」。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

3 x 3 的幻方是一个填充有 从 1 到 9  的不同数字的 3 x 3 矩阵，其中每行，每列以及两条对角线上的各数之和都相等。

给定一个由整数组成的row x col 的 grid，其中有多少个 3 × 3 的 “幻方” 子矩阵？

注意：虽然幻方只能包含 1 到 9 的数字，但 grid 可以包含最多15的数字。

 

示例 1：

输入: grid = [[4,3,8,4],[9,5,1,9],[2,7,6,2]
输出: 1
解释: 
下面的子矩阵是一个 3 x 3 的幻方：

而这一个不是：

总的来说，在本示例所给定的矩阵中只有一个 3 x 3 的幻方子矩阵。

示例 2:

输入: grid = [[8]]
输出: 0

 

提示:

• row == grid.length
• col == grid[i].length
• 1 <= row, col <= 10
• 0 <= grid[i][j] <= 15

幻方正中心一定是 5

$3\times 3$ 的幻方必须包含 $1$ 到 $9$ 所有数字，这意味着幻方元素和为 $1+2+\cdots + 9 = 45$。

由于每行的和都要相等，所以每行的和为 $\dfrac{45}{3} = 15$。这也是每列的和，对角线的和。

有 $4$ 条经过幻方正中心的线：第二行，第二列，两条对角线。

这 $4$ 条线：

• 覆盖了 $3\times 3$ 幻方的每个数，正中心的数覆盖了 $4$ 次（多覆盖了 $3$ 次），其余数恰好覆盖一次。
• 总和为 $15\cdot 4 = 60$。

设正中心的数为 $x$ ，则有

$$
1+2+\cdots + 9 + 3x = 60
$$

解得

$$
x = 5
$$

换言之（逆否命题），如果 $3\times 3$ 矩阵正中心的数不是 $5$，那么该矩阵必然不是幻方。

无需计算第三行的和，第三列的和

如果 $3\times 3$ 矩阵包含 $1$ 到 $9$ 所有整数，且前两行的和都是 $15$，那么第三行的和为

$$
1+2+\cdots+9-15-15 = 15
$$

同理，如果前两列的和都是 $15$，那么第三列的和必然是 $15$。

无需计算对角线的和

如果 $3\times 3$ 矩阵：

• 正中心的数是 $5$。
• 包含 $1$ 到 $9$ 所有整数。
• 前两行的和都是 $15$。
• 前两列的和都是 $15$。

下面证明：矩阵对角线的和一定都是 $15$。

设矩阵为

$$
\begin{bmatrix}
a & b & c \
d & 5 & f \
g & h & i \
\end{bmatrix}
$$

由于正中心的数是 $5$，只需证明对角两数之和等于 $10$，即 $a+i=c+g=10$。

在 $1$ 到 $9$ 中选两个不同整数相加等于 $10$，只有如下 $4$ 种情况：

• $1+9=10$。
• $2+8=10$。
• $3+7=10$。
• $4+6=10$。

由于已知 $b+h=d+f=10$，消耗了两种情况，剩余的四个数必然在 $a,c,g,i$ 中。比如 $b+h=1+9$，$d+f=3+7$，那么剩余的 $2,4,6,8$ 必然在 $a,c,g,i$ 中。

比如左上角的 $a=4$，那么 $6$ 在哪？

• 在右上角？此时 $a+c=10$，由于已知 $a+b+c=15$，得到 $b=5$，与正中心的数相同，矛盾。
• 在左下角？此时 $a+g=10$，由于已知 $a+d+g=15$，得到 $d=5$，与正中心的数相同，矛盾。
• 所以 $6$ 只能在右下角，即 $a+i=10$ 成立。
• 剩余两个数 $2$ 和 $8$ 在另一对角，所以 $c+g=10$ 成立。

用同样的方法可以证明，$a$ 等于其他数的时候，对角的数 $i$ 一定等于 $10-a$。剩余的另一对和为 $10$ 的数在另一对角。

综上，由已知条件可得，两条对角线的和都是 $15$。

如何快速判断矩阵包含 $1$ 到 $9$ 所有数？可以把数字压缩到一个二进制数 $\textit{mask}$ 中，$\textit{mask}$ 从低到高的 $i$ 位是 $1$ 表示 $i$ 在矩阵中。矩阵包含 $1$ 到 $9$ 所有数相当于 $\textit{mask} = 1111111110_{(2)} = 2^{10}-2=1022$。

###py

class Solution:
    def numMagicSquaresInside(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        ans = 0

        for i in range(m - 2):
            for j in range(n - 2):
                if grid[i + 1][j + 1] != 5:
                    continue

                mask = 0
                r_sum = [0] * 3
                c_sum = [0] * 3
                for r in range(3):
                    for c in range(3):
                        x = grid[i + r][j + c]
                        mask |= 1 << x
                        r_sum[r] += x
                        c_sum[c] += x

                if mask == 1022 and r_sum[0] == r_sum[1] == c_sum[0] == c_sum[1] == 15:
                    ans += 1

        return ans

###java

class Solution {
    public int numMagicSquaresInside(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int ans = 0;

        for (int i = 0; i < m - 2; i++) {
            for (int j = 0; j < n - 2; j++) {
                if (grid[i + 1][j + 1] != 5) {
                    continue;
                }

                int mask = 0;
                int[] rSum = new int[3];
                int[] cSum = new int[3];
                for (int r = 0; r < 3; r++) {
                    for (int c = 0; c < 3; c++) {
                        int x = grid[i + r][j + c];
                        mask |= 1 << x;
                        rSum[r] += x;
                        cSum[c] += x;
                    }
                }

                if (mask == (1 << 10) - 2 &&
                    rSum[0] == 15 && rSum[1] == 15 &&
                    cSum[0] == 15 && cSum[1] == 15) {
                    ans++;
                }
            }
        }

        return ans;
    }
}

###cpp

class Solution {
public:
    int numMagicSquaresInside(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        int ans = 0;

        for (int i = 0; i < m - 2; i++) {
            for (int j = 0; j < n - 2; j++) {
                if (grid[i + 1][j + 1] != 5) {
                    continue;
                }

                int mask = 0;
                int r_sum[3]{};
                int c_sum[3]{};
                for (int r = 0; r < 3; r++) {
                    for (int c = 0; c < 3; c++) {
                        int x = grid[i + r][j + c];
                        mask |= 1 << x;
                        r_sum[r] += x;
                        c_sum[c] += x;
                    }
                }

                if (mask == (1 << 10) - 2 &&
                    r_sum[0] == 15 && r_sum[1] == 15 &&
                    c_sum[0] == 15 && c_sum[1] == 15) {
                    ans++;
                }
            }
        }

        return ans;
    }
};

###c

int numMagicSquaresInside(int** grid, int gridSize, int* gridColSize) {
    int m = gridSize, n = gridColSize[0];
    int ans = 0;

    for (int i = 0; i < m - 2; i++) {
        for (int j = 0; j < n - 2; j++) {
            if (grid[i + 1][j + 1] != 5) {
                continue;
            }

            int mask = 0;
            int r_sum[3] = {};
            int c_sum[3] = {};
            for (int r = 0; r < 3; r++) {
                for (int c = 0; c < 3; c++) {
                    int x = grid[i + r][j + c];
                    mask |= 1 << x;
                    r_sum[r] += x;
                    c_sum[c] += x;
                }
            }

            if (mask == (1 << 10) - 2 &&
                r_sum[0] == 15 && r_sum[1] == 15 &&
                c_sum[0] == 15 && c_sum[1] == 15) {
                ans++;
            }
        }
    }

    return ans;
}

###go

func numMagicSquaresInside(grid [][]int) (ans int) {
m, n := len(grid), len(grid[0])
for i := range m - 2 {
for j := range n - 2 {
if grid[i+1][j+1] != 5 {
continue
}

mask := 0
var rSum, cSum [3]int
for r, row := range grid[i : i+3] {
for c, x := range row[j : j+3] {
mask |= 1 << x
rSum[r] += x
cSum[c] += x
}
}

if mask == 1<<10-2 &&
rSum[0] == 15 && rSum[1] == 15 &&
cSum[0] == 15 && cSum[1] == 15 {
ans++
}
}
}
return
}

###js

var numMagicSquaresInside = function (grid) {
    const m = grid.length;
    const n = grid[0].length;
    let ans = 0;

    for (let i = 0; i < m - 2; i++) {
        for (let j = 0; j < n - 2; j++) {
            if (grid[i + 1][j + 1] !== 5) {
                continue;
            }

            let mask = 0;
            const rSum = [0, 0, 0];
            const cSum = [0, 0, 0];
            for (let r = 0; r < 3; r++) {
                for (let c = 0; c < 3; c++) {
                    const x = grid[i + r][j + c];
                    mask |= 1 << x;
                    rSum[r] += x;
                    cSum[c] += x;
                }
            }

            if (mask === (1 << 10) - 2 &&
                rSum[0] === 15 && rSum[1] === 15 &&
                cSum[0] === 15 && cSum[1] === 15) {
                ans++;
            }
        }
    }

    return ans;
};

###rust

impl Solution {
    pub fn num_magic_squares_inside(grid: Vec<Vec<i32>>) -> i32 {
        let m = grid.len();
        let n = grid[0].len();
        let mut ans = 0;

        for i in 0..m.saturating_sub(2) {
            for j in 0..n.saturating_sub(2) {
                if grid[i + 1][j + 1] != 5 {
                    continue;
                }

                let mut mask = 0;
                let mut r_sum = [0; 3];
                let mut c_sum = [0; 3];
                for (r, row) in grid[i..i + 3].iter().enumerate() {
                    for (c, &x) in row[j..j + 3].iter().enumerate() {
                        mask |= 1 << x;
                        r_sum[r] += x;
                        c_sum[c] += x;
                    }
                }

                if mask == (1 << 10) - 2 &&
                    r_sum[0] == 15 && r_sum[1] == 15 &&
                    c_sum[0] == 15 && c_sum[1] == 15 {
                    ans += 1;
                }
            }
        }

        ans
    }
}

复杂度分析

• 时间复杂度：$\mathcal{O}(mn)$，其中 $m$ 和 $n$ 分别是 $\textit{grid}$ 的行数和列数。
• 空间复杂度：$\mathcal{O}(1)$。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

解题思路

首先谈谈三阶幻方，固然是可以通过定义去判断，但写起来很麻烦，效率也不高。实际上，三阶幻方的解是固定的，有以下八种。

自然是不可能逐个判断是不是这八个之一，大家仔细观察，相信很容易找出这八个解的共同点，首先中间的元素都是五，角上元素都是偶数，中点都是奇数。同一行的解可以通过旋转得到，第一行镜像，可以得到第二行。也就是说，三阶幻方本质只有一种解，其余都是旋转镜像的体现。
我们可以依据这一点，写出优雅简洁的代码。

1. 遍历中间的部分，只有是五的时候，才判断以他为中心的三阶方阵是否是幻方。
2. 五已经比对过了，只需要比对其他八个元素，由于解的旋转不变特性，这里将八个元素按顺序存放，方便后面比较，顺序如下图。
3. 解的编码，如何表示旋转镜像，参考旋转数组这题的思想，将前面部分的放在后面就达到了旋转的效果。镜像只需要反向迭代就好了。
   
   4.第二步输入的数组首位元素和8 6 2 4逐个比较决定可能的解，从编码的数组中取出正向镜像两个解比较是否其一，就可确定是否是幻方。

代码

###cpp

class Solution {
public:
    vector<int> m={8,1,6,7,2,9,4,3,8,1,6,7,2,9,4,3};
    int numMagicSquaresInside(vector<vector<int>>& grid) {
        int di[8]={-1,-1,-1,0,1,1,1,0};
        int dj[8]={-1,0,1,1,1,0,-1,-1};
        int count=0;
        for(int i=1;i<grid.size()-1;i++)
            for(int j=1;j<grid[0].size()-1;j++)
                if(grid[i][j]==5){
                    vector<int> around;
                    for(int k=0;k<8;k++)
                        around.push_back(grid[i+di[k]][j+dj[k]]);
                    count+=IsMagic(around);
                }
        return count;
    }
    bool IsMagic(vector<int>& v){
        for(int i=0;i<8;i+=2)
            if(m[i]==v[0])
            return v==vector<int>(m.begin()+i,m.begin()+i+8)
            ||v==vector<int>(m.rbegin()+7-i,m.rbegin()+15-i);
        return false;//奇数元素
    }
};

解题思路

满足幻方的条件必定是中间的数字为5,周围的数字为满足 1->6->7->2->9->4->3->8->1
的这种圆环结构,5的上下左右必定是 1、9、3、7(这四个数字都只能组成两组 15)
并且5的周围的数字其实都可以跳过,这里没作实现
1.利用数组的索引语义记录索引对应的下一个数字
2.若5的下一个值满足条件,且该值的下一行对应列满足条件,顺时针
若5的下一个值满足条件,且该值的上一行对应列满足条件,逆时针
3.总共判断6次即可(前两次已经判断过了)

代码

###java

class Solution {
    public int numMagicSquaresInside(int[][] grid) {
        //if(grid == null || grid.length < 3 || grid[1].length < 3)return 0;
        //由于是1~9的不同数字,那么必定是5在中间,并且其他数字满足顺时针或逆时针
        int[] check = {0,6,9,8,3,0,7,2,1,4};
        int result = 0;
        for(int i=1;i<grid.length-1;i++){
            for(int j=1;j<grid[0].length-1;j++){
                if(grid[i][j] == 5){
                    int next = grid[i][j+1];
                    switch(next){
                        case 1:
                        case 3:
                        case 7:
                        case 9:
                            if(check[next] == grid[i+1][j+1]){
                                if(each(grid,check,i+1,j+1,1))
                                    result++;
                            }else if(check[next] == grid[i-1][j+1]){
                                if(each(grid,check,i-1,j+1,-1))
                                    result++;
                            }
                    }
                    //5的后一位必定不用算    
                    j++;
                }
            }
        }
        return result;
    }

    public boolean each(int[][] grid,int[] check,int x,int y,int ward){
        int cur = grid[x][y];
        int next = check[cur];
        for(int i=y-2;y!=i;){
            if(grid[x][--y] != next)
                return false;
            cur = next;
            next = check[cur];
        }
        for(int i=x-2*ward;x!=i;){
            if(grid[x-=ward][y] != next)
                return false;
            cur = next;
            next = check[cur];
        }
        for(int i=y+2;y!=i;){
            if(grid[x][++y] != next)
                return false;
            cur = next;
            next = check[cur];
        }
        return true;       
    }
}

你正在把积木堆成金字塔。每个块都有一个颜色，用一个字母表示。每一行的块比它下面的行 少一个块 ，并且居中。

为了使金字塔美观，只有特定的 三角形图案 是允许的。一个三角形的图案由 两个块 和叠在上面的 单个块 组成。模式是以三个字母字符串的列表形式 allowed 给出的，其中模式的前两个字符分别表示左右底部块，第三个字符表示顶部块。

• 例如，"ABC" 表示一个三角形图案，其中一个 “C” 块堆叠在一个 'A' 块(左)和一个 'B' 块(右)之上。请注意，这与 "BAC" 不同，"B" 在左下角，"A" 在右下角。

你从作为单个字符串给出的底部的一排积木 bottom 开始，必须 将其作为金字塔的底部。

在给定 bottom 和 allowed 的情况下，如果你能一直构建到金字塔顶部，使金字塔中的 每个三角形图案 都是在 allowed 中的，则返回 true ，否则返回 false 。

 

示例 1：

输入：bottom = "BCD", allowed = ["BCC","CDE","CEA","FFF"]
输出：true
解释：允许的三角形图案显示在右边。
从最底层(第 3 层)开始，我们可以在第 2 层构建“CE”，然后在第 1 层构建“E”。
金字塔中有三种三角形图案，分别是 “BCC”、“CDE” 和 “CEA”。都是允许的。

示例 2：

输入：bottom = "AAAA", allowed = ["AAB","AAC","BCD","BBE","DEF"]
输出：false
解释：允许的三角形图案显示在右边。
从最底层(即第 4 层)开始，创造第 3 层有多种方法，但如果尝试所有可能性，你便会在创造第 1 层前陷入困境。

 

提示：

• 2 <= bottom.length <= 6
• 0 <= allowed.length <= 216
• allowed[i].length == 3
• 所有输入字符串中的字母来自集合 {'A', 'B', 'C', 'D', 'E', 'F'}。
•  allowed 中所有值都是 唯一的

写一个类似 17. 电话号码的字母组合 的回溯（搜索）。从下往上，从左到右，枚举金字塔的每个格子填什么字母。

{:width=600px}

比如 $\textit{allowed}$ 中有 $\texttt{AAB}$ 和 $\texttt{AAC}$，那么当 $(i+1,j)$ 和 $(i+1,j+1)$ 都填 $\texttt{A}$ 的时候，$(i,j)$ 可以填 $\texttt{B}$，也可以填 $\texttt{C}$。枚举填哪个。

为了快速知道 $\texttt{AA}\to [\texttt{B}, \texttt{C}]$ 的对应关系，可以把 $\textit{allowed}$ 用哈希表（或者二维数组）分组，把 $\textit{allowed}[i]$ 前两个字母对应的第三个字母，记录在一个列表中。

优化前

###py

class Solution:
    def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool:
        groups = defaultdict(list)  # 三角形底部两个字母 -> [三角形顶部字母]
        for s in allowed:
            groups[s[:2]].append(s[2])

        n = len(bottom)
        pyramid = [[''] * (i + 1) for i in range(n)]
        pyramid[-1] = bottom

        # 现在准备填 (i, j) 这个格子
        # 返回继续填能否填完所有格子（从下往上填，每行从左到右填）
        def dfs(i: int, j: int) -> bool:
            if i < 0:  # 所有格子都已填完
                return True

            if j == i + 1:  # i 行已填完
                return dfs(i - 1, 0)  # 开始填 i-1 行

            # 枚举 (i, j) 填什么字母
            # 这取决于 (i+1, j) 和 (i+1, j+1) 填的字母
            for top in groups[pyramid[i + 1][j] + pyramid[i + 1][j + 1]]:
                pyramid[i][j] = top
                if dfs(i, j + 1):
                    return True
            return False

        # 从倒数第二行开始填
        return dfs(n - 2, 0)

###java

class Solution {
    public boolean pyramidTransition(String bottom, List<String> allowed) {
        // 三角形底部两个字母 -> [三角形顶部字母]
        List<Character>[][] groups = new ArrayList[6][6];
        for (List<Character>[] row : groups) {
            Arrays.setAll(row, _ -> new ArrayList<>());
        }
        for (String S : allowed) {
            char[] s = S.toCharArray();
            groups[s[0] - 'A'][s[1] - 'A'].add(s[2]);
        }

        int n = bottom.length();
        char[][] pyramid = new char[n][];
        for (int i = 0; i < n - 1; i++) {
            pyramid[i] = new char[i + 1];
        }
        pyramid[n - 1] = bottom.toCharArray();

        // 从倒数第二行开始填
        return dfs(n - 2, 0, pyramid, groups);
    }

    // 现在准备填 (i, j) 这个格子
    // 返回继续填能否填完所有格子（从下往上填，每行从左到右填）
    private boolean dfs(int i, int j, char[][] pyramid, List<Character>[][] groups) {
        if (i < 0) { // 所有格子都已填完
            return true;
        }

        if (j == i + 1) { // i 行已填完
            return dfs(i - 1, 0, pyramid, groups); // 开始填 i-1 行
        }

        // 枚举 (i, j) 填什么字母
        // 这取决于 (i+1, j) 和 (i+1, j+1) 填的字母
        for (char top : groups[pyramid[i + 1][j] - 'A'][pyramid[i + 1][j + 1] - 'A']) {
            pyramid[i][j] = top;
            if (dfs(i, j + 1, pyramid, groups)) {
                return true;
            }
        }
        return false;
    }
}

###cpp

class Solution {
public:
    bool pyramidTransition(string bottom, vector<string>& allowed) {
        string groups[6][6]{}; // 三角形底部两个字母 -> [三角形顶部字母]
        for (auto& s : allowed) {
            groups[s[0] - 'A'][s[1] - 'A'] += s[2];
        }

        int n = bottom.size();
        vector<string> pyramid(n);
        for (int i = 0; i < n - 1; i++) {
            pyramid[i].resize(i + 1);
        }
        pyramid[n - 1] = move(bottom);

        // 现在准备填 (i, j) 这个格子
        // 返回继续填能否填完所有格子（从下往上填，每行从左到右填）
        auto dfs = [&](this auto&& dfs, int i, int j) -> bool {
            if (i < 0) { // 所有格子都已填完
                return true;
            }

            if (j == i + 1) { // i 行已填完
                return dfs(i - 1, 0); // 开始填 i-1 行
            }

            // 枚举 (i, j) 填什么字母
            // 这取决于 (i+1, j) 和 (i+1, j+1) 填的字母
            for (char top : groups[pyramid[i + 1][j] - 'A'][pyramid[i + 1][j + 1] - 'A']) {
                pyramid[i][j] = top;
                if (dfs(i, j + 1)) {
                    return true;
                }
            }
            return false;
        };

        // 从倒数第二行开始填
        return dfs(n - 2, 0);
    }
};

###go

func pyramidTransition(bottom string, allowed []string) bool {
groups := [6][6][]byte{} // 三角形底部两个字母 -> [三角形顶部字母]
for _, s := range allowed {
a, b := s[0]-'A', s[1]-'A'
groups[a][b] = append(groups[a][b], s[2])
}

n := len(bottom)
pyramid := make([][]byte, n)
for i := range n - 1 {
pyramid[i] = make([]byte, i+1)
}
pyramid[n-1] = []byte(bottom)

// 现在准备填 (i, j) 这个格子
// 返回继续填能否填完所有格子（从下往上填，每行从左到右填）
var dfs func(int, int) bool
dfs = func(i, j int) bool {
if i < 0 { // 所有格子都已填完
return true
}

if j == i+1 { // i 行已填完
return dfs(i-1, 0) // 开始填 i-1 行
}

// 枚举 (i, j) 填什么字母
// 这取决于 (i+1, j) 和 (i+1, j+1) 填的字母
for _, top := range groups[pyramid[i+1][j]-'A'][pyramid[i+1][j+1]-'A'] {
pyramid[i][j] = top
if dfs(i, j+1) {
return true
}
}
return false
}

// 从倒数第二行开始填
return dfs(n-2, 0)
}

复杂度分析

• 时间复杂度：$\mathcal{O}(|\Sigma|^{n^2})$，其中 $n$ 是 $\textit{bottom}$ 的长度，$|\Sigma|=6$ 是字符集合的大小。搜索树的高度为 $\mathcal{O}(n^2)$，每个节点至多有 $|\Sigma|$ 个儿子，所以搜索树有 $\mathcal{O}(|\Sigma|^{n^2})$ 个节点，遍历这棵搜索树需要 $\mathcal{O}(|\Sigma|^{n^2})$ 的时间。
• 空间复杂度：$\mathcal{O}(m + n^2)$，其中 $m$ 是 $\textit{allowed}$ 的长度。

优化一：减少重复搜索

{:width=600px}

###py

class Solution:
    def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool:
        groups = defaultdict(list)
        for s in allowed:
            groups[s[:2]].append(s[2])

        n = len(bottom)
        pyramid = [[''] * (i + 1) for i in range(n)]
        pyramid[-1] = bottom

        vis = set()  # 访问标记

        def dfs(i: int, j: int) -> bool:
            if i < 0:
                return True

            if j == i + 1:
                row = ''.join(pyramid[i])
                if row in vis:  # 这一行之前填过一模一样的，继续填，没能填到塔顶
                    return False  # 直接返回
                vis.add(row)
                return dfs(i - 1, 0)

            for top in groups[pyramid[i + 1][j] + pyramid[i + 1][j + 1]]:
                pyramid[i][j] = top
                if dfs(i, j + 1):
                    return True
            return False

        return dfs(n - 2, 0)

###java

class Solution {
    public boolean pyramidTransition(String bottom, List<String> allowed) {
        List<Character>[][] groups = new ArrayList[6][6];
        for (List<Character>[] row : groups) {
            Arrays.setAll(row, _ -> new ArrayList<>());
        }
        for (String S : allowed) {
            char[] s = S.toCharArray();
            groups[s[0] - 'A'][s[1] - 'A'].add(s[2]);
        }

        int n = bottom.length();
        char[][] pyramid = new char[n][];
        for (int i = 0; i < n - 1; i++) {
            pyramid[i] = new char[i + 1];
        }
        pyramid[n - 1] = bottom.toCharArray();

        Set<String> vis = new HashSet<>(); // 访问标记

        return dfs(n - 2, 0, pyramid, vis, groups);
    }

    private boolean dfs(int i, int j, char[][] pyramid, Set<String> vis, List<Character>[][] groups) {
        if (i < 0) {
            return true;
        }

        if (j == i + 1) {
            String row = new String(pyramid[i]);
            if (!vis.add(row)) { // 这一行之前填过一模一样的，继续填，没能填到塔顶
                return false; // 直接返回
            }
            return dfs(i - 1, 0, pyramid, vis, groups);
        }

        for (char top : groups[pyramid[i + 1][j] - 'A'][pyramid[i + 1][j + 1] - 'A']) {
            pyramid[i][j] = top;
            if (dfs(i, j + 1, pyramid, vis, groups)) {
                return true;
            }
        }
        return false;
    }
}

###cpp

class Solution {
public:
    bool pyramidTransition(string bottom, vector<string>& allowed) {
        string groups[6][6];
        for (auto& s : allowed) {
            groups[s[0] - 'A'][s[1] - 'A'] += s[2];
        }

        int n = bottom.size();
        vector<string> pyramid(n);
        for (int i = 0; i < n - 1; i++) {
            pyramid[i].resize(i + 1);
        }
        pyramid[n - 1] = move(bottom);

        unordered_set<string> vis; // 访问标记

        auto dfs = [&](this auto&& dfs, int i, int j) -> bool {
            if (i < 0) {
                return true;
            }

            if (j == i + 1) {
                if (!vis.insert(pyramid[i]).second) { // 这一行之前填过一模一样的，继续填，没能填到塔顶
                    return false; // 直接返回
                }
                return dfs(i - 1, 0);
            }

            for (char top : groups[pyramid[i + 1][j] - 'A'][pyramid[i + 1][j + 1] - 'A']) {
                pyramid[i][j] = top;
                if (dfs(i, j + 1)) {
                    return true;
                }
            }
            return false;
        };

        return dfs(n - 2, 0);
    }
};

###go

func pyramidTransition(bottom string, allowed []string) bool {
groups := [6][6][]byte{}
for _, s := range allowed {
a, b := s[0]-'A', s[1]-'A'
groups[a][b] = append(groups[a][b], s[2])
}

n := len(bottom)
pyramid := make([][]byte, n)
for i := range n - 1 {
pyramid[i] = make([]byte, i+1)
}
pyramid[n-1] = []byte(bottom)

vis := map[string]struct{}{} // 访问标记

var dfs func(int, int) bool
dfs = func(i, j int) bool {
if i < 0 {
return true
}

if j == i+1 {
row := string(pyramid[i])
if _, ok := vis[row]; ok { // 这一行之前填过一模一样的，继续填，没能填到塔顶
return false // 直接返回
}
vis[row] = struct{}{}
return dfs(i-1, 0)
}

for _, top := range groups[pyramid[i+1][j]-'A'][pyramid[i+1][j+1]-'A'] {
pyramid[i][j] = top
if dfs(i, j+1) {
return true
}
}
return false
}

return dfs(n-2, 0)
}

优化二：减少更多重复搜索

{:width=600px}

###py

class Solution:
    def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool:
        groups = defaultdict(list)
        for s in allowed:
            groups[s[:2]].append(s[2])

        n = len(bottom)
        pyramid = [[] for _ in range(n)]
        pyramid[-1] = bottom

        vis = set()

        def dfs(i: int, j: int) -> bool:
            if i < 0:
                return True

            row = ''.join(pyramid[i])
            if row in vis:  # 之前填过一模一样的，这个局部的金字塔无法填完
                return False  # 继续递归也无法填完，直接返回

            if j == i + 1:
                vis.add(row)
                return dfs(i - 1, 0)

            for top in groups[pyramid[i + 1][j] + pyramid[i + 1][j + 1]]:
                pyramid[i].append(top)
                if dfs(i, j + 1):
                    return True
                pyramid[i].pop()
            return False

        return dfs(n - 2, 0)

###java

class Solution {
    public boolean pyramidTransition(String bottom, List<String> allowed) {
        List<Character>[][] groups = new ArrayList[6][6];
        for (List<Character>[] row : groups) {
            Arrays.setAll(row, _ -> new ArrayList<>());
        }
        for (String S : allowed) {
            char[] s = S.toCharArray();
            groups[s[0] - 'A'][s[1] - 'A'].add(s[2]);
        }

        int n = bottom.length();
        char[][] pyramid = new char[n][];
        for (int i = 0; i < n - 1; i++) {
            pyramid[i] = new char[i + 1];
        }
        pyramid[n - 1] = bottom.toCharArray();

        Set<String> vis = new HashSet<>();

        return dfs(n - 2, 0, pyramid, vis, groups);
    }

    private boolean dfs(int i, int j, char[][] pyramid, Set<String> vis, List<Character>[][] groups) {
        if (i < 0) {
            return true;
        }

        String row = new String(pyramid[i], 0, j);
        if (vis.contains(row)) { // 之前填过一模一样的，这个局部的金字塔无法填完
            return false; // 继续递归也无法填完，直接返回
        }

        if (j == i + 1) {
            vis.add(row);
            return dfs(i - 1, 0, pyramid, vis, groups);
        }

        for (char top : groups[pyramid[i + 1][j] - 'A'][pyramid[i + 1][j + 1] - 'A']) {
            pyramid[i][j] = top;
            if (dfs(i, j + 1, pyramid, vis, groups)) {
                return true;
            }
        }
        return false;
    }
}

###cpp

class Solution {
public:
    bool pyramidTransition(string bottom, vector<string>& allowed) {
        string groups[6][6];
        for (auto& s : allowed) {
            groups[s[0] - 'A'][s[1] - 'A'] += s[2];
        }

        int n = bottom.size();
        vector<string> pyramid(n);
        pyramid[n - 1] = move(bottom);

        unordered_set<string> vis;

        auto dfs = [&](this auto&& dfs, int i, int j) -> bool {
            if (i < 0) {
                return true;
            }

            if (vis.contains(pyramid[i])) { // 之前填过一模一样的，这个局部的金字塔无法填完
                return false; // 继续递归也无法填完，直接返回
            }

            if (j == i + 1) {
                vis.insert(pyramid[i]);
                return dfs(i - 1, 0);
            }

            for (char top : groups[pyramid[i + 1][j] - 'A'][pyramid[i + 1][j + 1] - 'A']) {
                pyramid[i] += top;
                if (dfs(i, j + 1)) {
                    return true;
                }
                pyramid[i].pop_back();
            }
            return false;
        };

        return dfs(n - 2, 0);
    }
};

###go

func pyramidTransition(bottom string, allowed []string) bool {
groups := [6][6][]byte{}
for _, s := range allowed {
a, b := s[0]-'A', s[1]-'A'
groups[a][b] = append(groups[a][b], s[2])
}

n := len(bottom)
pyramid := make([][]byte, n)
for i := range n - 1 {
pyramid[i] = make([]byte, i+1)
}
pyramid[n-1] = []byte(bottom)

vis := map[string]struct{}{}

var dfs func(int, int) bool
dfs = func(i, j int) bool {
if i < 0 {
return true
}

row := string(pyramid[i][:j])
if _, ok := vis[row]; ok { // 之前填过一模一样的，这个局部的金字塔无法填完
return false // 继续递归也无法填完，直接返回
}

if j == i+1 {
vis[row] = struct{}{}
return dfs(i-1, 0)
}

for _, top := range groups[pyramid[i+1][j]-'A'][pyramid[i+1][j+1]-'A'] {
pyramid[i][j] = top
if dfs(i, j+1) {
return true
}
}
return false
}

return dfs(n-2, 0)
}

复杂度分析

• 时间复杂度：$\mathcal{O}(n|\Sigma|^n)$，其中 $n$ 是 $\textit{bottom}$ 的长度，$|\Sigma|=6$ 是字符集合的大小。把字符串按照长度分类，长为 $k$ 的字符串至多有 $|\Sigma|^k$ 个。等比数列求和 $|\Sigma| + |\Sigma|^2 + \cdots + |\Sigma|^{n-1} = \mathcal{O}(|\Sigma|^n)$。一共有 $\mathcal{O}(|\Sigma|^n)$ 个字符串，每个字符串花费 $\mathcal{O}(n)$ 的时间与 $\textit{vis}$ 交互（查询，插入）。
• 空间复杂度：$\mathcal{O}(n|\Sigma|^n)$。$\textit{vis}$ 保存了 $\mathcal{O}(|\Sigma|^n)$ 个字符串，每个字符串需要 $\mathcal{O}(n)$ 的空间。

优化三：位运算

把 $\texttt{A}$ 到 $\texttt{F}$ 映射为 $1$ 到 $6$。由于每个字母只占用 $3$ 个比特位，可以用二进制数表示字符串。

由于倒数第二排最多 $5$ 个字母，所以记录到 $\textit{vis}$ 中的二进制数的长度最多为 $15$。

问：为什么不映射为 $0$ 到 $5$？

答：比如，我们无法区分 $\texttt{AA}$ 和 $\texttt{AAA}$，二者都是 $0$。

###py

class Solution:
    def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool:
        groups = [[[] for _ in range(7)] for _ in range(7)]
        for a, b, c in allowed:
            # A~F -> 1~6
            groups[ord(a) & 31][ord(b) & 31].append(ord(c) & 31)

        n = len(bottom)
        pyramid = [0] * n
        for i, ch in enumerate(bottom):
            pyramid[-1] |= (ord(ch) & 31) << (i * 3)  # 等价于 pyramid[-1][i] = ord(ch)&31

        vis = set()

        def dfs(i: int, j: int) -> bool:
            if i < 0:
                return True

            if pyramid[i] in vis:
                return False

            if j == i + 1:
                vis.add(pyramid[i])
                return dfs(i - 1, 0)

            for top in groups[pyramid[i + 1] >> (j * 3) & 7][pyramid[i + 1] >> ((j + 1) * 3) & 7]:
                pyramid[i] &= ~(7 << (j * 3))  # 清除之前填的字母，等价于 pyramid[i][j] = 0
                pyramid[i] |= top << (j * 3)  # 等价于 pyramid[i][j] = top
                if dfs(i, j + 1):
                    return True
            return False

        return dfs(n - 2, 0)

###java

class Solution {
    public boolean pyramidTransition(String bottom, List<String> allowed) {
        List<Integer>[][] groups = new ArrayList[7][7];
        for (List<Integer>[] row : groups) {
            Arrays.setAll(row, _ -> new ArrayList<>());
        }
        for (String S : allowed) {
            char[] s = S.toCharArray();
            // A~F -> 1~6
            groups[s[0] & 31][s[1] & 31].add(s[2] & 31);
        }

        char[] s = bottom.toCharArray();
        int n = s.length;
        int[] pyramid = new int[n];
        for (int i = 0; i < n; i++) {
            pyramid[n - 1] |= (s[i] & 31) << (i * 3); // 等价于 pyramid[n-1][i] = s[i]&31
        }

        boolean[] vis = new boolean[1 << ((n - 1) * 3)];

        return dfs(n - 2, 0, pyramid, vis, groups);
    }

    private boolean dfs(int i, int j, int[] pyramid, boolean[] vis, List<Integer>[][] groups) {
        if (i < 0) {
            return true;
        }

        if (vis[pyramid[i]]) {
            return false;
        }

        if (j == i + 1) {
            vis[pyramid[i]] = true;
            return dfs(i - 1, 0, pyramid, vis, groups);
        }

        for (int top : groups[pyramid[i + 1] >> (j * 3) & 7][pyramid[i + 1] >> ((j + 1) * 3) & 7]) {
            pyramid[i] &= ~(7 << (j * 3)); // 清除之前填的字母，等价于 pyramid[i][j] = 0
            pyramid[i] |= top << (j * 3); // 等价于 pyramid[i][j] = top
            if (dfs(i, j + 1, pyramid, vis, groups)) {
                return true;
            }
        }
        return false;
    }
}

###cpp

class Solution {
public:
    bool pyramidTransition(string bottom, vector<string>& allowed) {
        vector<int> groups[7][7];
        for (auto& s : allowed) {
            // A~F -> 1~6
            groups[s[0] & 31][s[1] & 31].push_back(s[2] & 31);
        }

        int n = bottom.size();
        vector<int> pyramid(n);
        for (int i = 0; i < n; i++) {
            pyramid[n - 1] |= (bottom[i] & 31) << (i * 3); // 等价于 pyramid[n-1][i] = bottom[i]&31
        }

        vector<uint8_t> vis(1 << ((n - 1) * 3));

        auto dfs = [&](this auto&& dfs, int i, int j) -> bool {
            if (i < 0) {
                return true;
            }

            if (vis[pyramid[i]]) {
                return false;
            }

            if (j == i + 1) {
                vis[pyramid[i]] = true;
                return dfs(i - 1, 0);
            }

            for (int top : groups[pyramid[i + 1] >> (j * 3) & 7][pyramid[i + 1] >> ((j + 1) * 3) & 7]) {
                pyramid[i] &= ~(7 << (j * 3)); // 清除之前填的字母，等价于 pyramid[i][j] = 0
                pyramid[i] |= top << (j * 3); // 等价于 pyramid[i][j] = top
                if (dfs(i, j + 1)) {
                    return true;
                }
            }
            return false;
        };

        return dfs(n - 2, 0);
    }
};

###go

func pyramidTransition(bottom string, allowed []string) bool {
groups := [7][7][]byte{}
for _, s := range allowed {
a, b := s[0]&31, s[1]&31 // A~F -> 1~6
groups[a][b] = append(groups[a][b], s[2]&31)
}

n := len(bottom)
pyramid := make([]int, n)
for i, ch := range bottom {
pyramid[n-1] |= int(ch&31) << (i * 3) // 等价于 pyramid[n-1][i] = ch&31
}

vis := make([]bool, 1<<((n-1)*3))

var dfs func(int, int) bool
dfs = func(i, j int) bool {
if i < 0 {
return true
}

if vis[pyramid[i]] {
return false
}

if j == i+1 {
vis[pyramid[i]] = true
return dfs(i-1, 0)
}

for _, top := range groups[pyramid[i+1]>>(j*3)&7][pyramid[i+1]>>((j+1)*3)&7] {
pyramid[i] &^= 7 << (j * 3) // 清除之前填的字母，等价于 pyramid[i][j] = 0
pyramid[i] |= int(top) << (j * 3) // 等价于 pyramid[i][j] = top
if dfs(i, j+1) {
return true
}
}
return false
}

return dfs(n-2, 0)
}

复杂度分析

• 时间复杂度：$\mathcal{O}(|\Sigma|^n)$，其中 $n$ 是 $\textit{bottom}$ 的长度，$|\Sigma|=6$ 是字符集合的大小。
• 空间复杂度：$\mathcal{O}(|\Sigma|^n)$。

专题训练

见下面回溯题单的「§4.7 搜索」。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

"ABBBBBBG"
["BDD","BFB","FDA","CCC","FBD","FBG","EEB","GBA","CFB","ECB","GDA","ECC","EFE","FCA","DBA","FAD","BEE","GEC","CFC","CFD","BCG","CAC","FCC","GAC","CAG","CFF","BEC","EAD","GBE","FEG","BDC","GBF","FBB","FBE","DDG","FDF","EDF","FAF","BEB","DDE","EEA","FAG","GDC","DFE","CDB","DFD","GDD","DAF","ECE","DBG","DDD","EFG","FAC","FEC","GED","DEE","CCF","EFD","FDE","GDF","ECG","DAE","FCG","DCA","EAF","EED","EEE","FEA","BFG","EAA","GDE","CEB","FAE","BDE","EBB","GFD","DBB","BFD","EFF","DAD","CDC","DCD","FFD","DBD","EFA","BCB","ECF","CFA","GFF","CFG","EEG","DAG","CAE","FED","CCA","EDE","FDG","BEF","FDD","BEG","FFE","DDC","BCE","GAA","GFE","FFF","CFE","BDF","DFG","DEF","FEF","GEE","EAB","GDB","CEE","BDA","DEG","DEC","GCG","DFB","EFB","GAB","CDF","CAF","BAB","GCC","DDA","CDD","FCB","DAA","GBG","BAC","GCE","GAG","EAE","EBG","GBD","BFE","CCD","EDD","FCD","FBC","DEB","EDG","GEA","EBE","GDG","DBE","BCD","GBB","FEB","DED","CAD","EDB","CED","GCD","BFC","GAE","CEG","EEC","FEE","GCA","FCF","ECD","DCC","BDB","EBD","DCE","BAE","FFG","DDF","DCF","BED","CAA","BCF","GBC","CCB","BCC","GFC","FFB","DFA","BBA","BBB","BBC","BBD","BBE","BBF","BBG","AAA","ABA","ACA","ADA","AEA","AFA","BGG","CGG","DGG","EGG","FGG","GGG"]

回溯法能过的唯一原因是数据太弱。

上面的测试用例的构造思路是这样的：形如A*的如AA,AB,AC...，但除AG以外，都只能放A，形如*G如BG,CG,...，但除AG以外，都只能放G。AG上没有能放的字母。其他组合上面能放几乎所有字母。

可以看出来对这个例子来说，每一层最左边只能是A，最右边只能是G，倒数第二层只能是AG，而AG上不能放字母，因此无解。但是所有的解都是在最后一步才失败的，因此遍历过的状态数极其巨大。

以官方题解为例，官方题解主要包括朴素的回溯和按行去重两种方法。朴素回溯的复杂度是O(A^(N^2))，而非题解说的O(A^N)，对于这个测试例来说，无论C++还是Java都会炸，Python就更不用说了。

按行去重也就是官方Java题解中用的方法，遇到整行的时候会缓存整行的结果，这可以将复杂度降至O(A^(2N))，差的这一点可以让Java通过（Java用位运算hash的方式常数也比较低），但是官方题解的Python即使打开seen的hash也会炸。

能通过的方法是将中途所有的状态都保存下来去重。每次尝试在下一层两个字母上堆一个字母的时候，下一层有一个字母就被压到底部了，它与后续求解无关，因此当前状态永远可以用上一层已经堆上的字母 + 下一层仍然露出来的字母来表示，总的状态数是O(NA^N)，正好在可以通过的范围内。

###python3

from functools import lru_cache


class Solution:
    def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool:
        trans = {}
        for p in allowed:
            trans.setdefault(p[:2], []).append(p[2])

        @lru_cache(None)
        def search(a, b):
            if len(a) == 2:
                if not b:
                    return a in trans
                else:
                    return any(search(b + t, '') for t in trans.get(a, []))
            else:
                return any(search(a[1:], b + t) for t in trans.get(a[:2], []))

        return search(bottom, '')

事实上这并不是最强的测试例，以下测试例耗时会更长：

"ADDDDDDA"
["ADA","ADB","ADC","AEA","AEB","AEC","AFA","AFB","AFC","AGA","AGB","AGC","BDA","BDB","BDC","BEA","BEB","BEC","BFA","BFB","BFC","BGA","BGB","BGC","CDA","CDB","CDC","CEA","CEB","CEC","CFA","CFB","CFC","CGA","CGB","CGC","DAA","DAB","DAC","DBA","DBB","DBC","DCA","DCB","DCC","EAA","EAB","EAC","EBA","EBB","EBC","ECA","ECB","ECC","FAA","FAB","FAC","FBA","FBB","FBC","FCA","FCB","FCC","GAA","GAB","GAC","GBA","GBB","GBC","GCA","GCB","GCC","DDA","DDB","DDC","DEA","DEB","DEC","DFA","DFB","DFC","DGA","DGB","DGC","EDA","EDB","EDC","EEA","EEB","EEC","EFA","EFB","EFC","EGA","EGB","EGC","FDA","FDB","FDC","FEA","FEB","FEC","FFA","FFB","FFC","FGA","FGB","FGC","GDA","GDB","GDC","GEA","GEB","GEC","GFA","GFB","GFC","GGA","GGB","GGC","DDD","DDE","DDF","DDG","DED","DEE","DEF","DEG","DFD","DFE","DFF","DFG","DGD","DGE","DGF","DGG","EDD","EDE","EDF","EDG","EED","EEE","EEF","EEG","EFD","EFE","EFF","EFG","EGD","EGE","EGF","EGG","FDD","FDE","FDF","FDG","FED","FEE","FEF","FEG","FFD","FFE","FFF","FFG","FGD","FGE","FGF","FGG","GDD","GDE","GDF","GDG","GED","GEE","GEF","GEG","GFD","GFE","GFF","GFG","GGD","GGE","GGF","GGG"]

"ADDDDDDA"
["GDF","EFB","FFC","DCB","GFD","GCD","BGA","EEC","DEC","EDD","CDA","FEF","CGD","ECA","DGD","FFD","BEA","GEE","EDE","CED","GEF","BCA","CFB","GGA","GGB","FDE","FGE","GAB","FBA","FFA","ECF","FDA","CCD","CGA","DED","EBB","FFG","BFB","FCB","DGE","DDB","BEB","GDG","FDB","FFB","CGB","GFE","FEG","FDC","CDF","GCE","DFD","DFG","CCA","GFA","FCE","BDA","ACA","CDB","GDE","EEA","FBB","FEC","DCA","FAB","CCE","GGF","CAA","EEF","CDD","FGA","DDC","CGC","DFF","CEE","EDC","FCA","GBB","CEC","DEE","DEB","AFB","EEG","FGB","FCD","GFC","GCA","DDD","FGC","ECC","FDF","GEC","DBB","DFB","EED","GAA","FGD","DBA","DCD","EBA","FCF","ECG","CDE","DCE","EAA","DAB","FDD","DFC","GGD","BGB","CBA","GDC","AGB","BFA","EFD","EGA","FAA","GEG","EAB","EDA","DEA","CEA","DCC","GCG","DAA","ECD","GFB","GBA","GCF","EEE","AFA","EGC","AGA","FEB","CCF","DGA","FFF","CCB","DDA","BCB","ADA","ECB","DGG","EGE","CFC","GCC","FGF","FDG","CGF","DDE","AEB","GGG","CCC","DCG","DDG","CEF","FGG","ACB","DFE","BDB","CCG","CGG","CFG","DGC","EFC","GDB","FEE","EDB","CFF","EFF","FEA","EFE","GEA","CDC","EDF","CGE","CFA","GGC","DEG","FCC","FFE","CFD","EDG","CAB","CEB","GDA","EGB","ECE","GCB","DGF","DGB","EGF","EGG","CEG","GFG","ADB","EFA","GFF","DEF","GEB"]

"AGGGGGGA"
["AFA","AFB","AFC","AFD","AFE","AGA","AGB","AGC","AGD","AGE","BFA","BFB","BFC","BFD","BFE","BGA","BGB","BGC","BGD","BGE","CFA","CFB","CFC","CFD","CFE","CGA","CGB","CGC","CGD","CGE","DFA","DFB","DFC","DFD","DFE","DGA","DGB","DGC","DGD","DGE","EFA","EFB","EFC","EFD","EFE","EGA","EGB","EGC","EGD","EGE","FAA","FAB","FAC","FAD","FAE","FBA","FBB","FBC","FBD","FBE","FCA","FCB","FCC","FCD","FCE","FDA","FDB","FDC","FDD","FDE","FEA","FEB","FEC","FED","FEE","GAA","GAB","GAC","GAD","GAE","GBA","GBB","GBC","GBD","GBE","GCA","GCB","GCC","GCD","GCE","GDA","GDB","GDC","GDD","GDE","GEA","GEB","GEC","GED","GEE","FFA","FFB","FFC","FFD","FFE","FGA","FGB","FGC","FGD","FGE","GFA","GFB","GFC","GFD","GFE","GGA","GGB","GGC","GGD","GGE","FFF","FFG","FGF","FGG","GFF","GFG","GGF","GGG"]

这两个测试例的构造思路是，将字母分成两类，一类是Type-0，一类是Type-1。0和0上不能放数字，0和1、1和0上只能放0类数字，而1和1上能放全部数字。然后给出的串两侧是Type-0字母，中间全部是Type-1字母。区别在于第一个使用ABC作为Type-0，第二个使用ABCD，第三个使用ABCDE。别看ABCDE时的allow数组似乎最短，但它对前面的算法威胁是最大的，因为最前面的测试例每一行两侧的字母固定是A和G，而这个例子中两侧的字母可以选择的数量更多，每一行中中间可以使用所有字母，两侧只能用Type-0，因此最后一个测试例的状态数是文章最开始测试例状态数的25倍。

这三个测试例可以炸掉LeetCode的标程，让标程超时（标程大概就是官方题解中记忆化的Java版本）。最后一个测试例可以炸掉上面的Python答案（如果改用Java或C++估计可以通过）。

在前面答案的基础上进行提前剪枝，可以减少状态数，通过这几个测试例：

###python3

from functools import lru_cache


class Solution:
    def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool:
        trans = {}
        for p in allowed:
            trans.setdefault(p[:2], []).append(p[2])

        @lru_cache(None)
        def search(a, b):
            if len(b) >= 2:
                if not search(b, ''):
                    return False
            if len(a) == 2:
                if not b:
                    return a in trans
                else:
                    return any(search(b + t, '') for t in trans.get(a, []))
            else:
                return any(search(a[1:], b + t) for t in trans.get(a[:2], []))

        return search(bottom, '')

注意到在处理(a,b)时，提前判断了(b,'')是否可行。这个判断对题目最开始的测试例没有太大帮助，但对后面这几个测试例有一定作用，主要是有效防止枚举出Type-0字符。目前没有已知的测试例可以fail这个程序了。

解题思路

1.首先为allowed数组建立一个哈希表，键为下面的两块砖头，值为上面的砖头。注意，同样的下方砖头可能允许不同的上方砖头（例如ABC和ABD），故哈希表的值用vector。
2.递归函数gogogo接受三个参数，第一个bottom为目前检查的层，upper为已经形成的部分下一层，pos为目前bottom已经检查到了第几块砖头。
3.gogogo中，若pos == bottom.size()-1，说明这一层已经检查完毕啦，故将upper设为新的待检查层，注意哦，若upper.size()为1，说明已经到顶啦，返回true即可。
4.若下一个位置不存在可以放置的砖块，即vc.empty()，则返回false。否则，尝试所有可以放置的砖块。

代码

###cpp

class Solution {
public:
    unordered_map<string, vector<char>> mp;       
    bool pyramidTransition(string bottom, vector<string>& allowed) {
        for(string str:allowed){
            mp[str.substr(0, 2)].push_back(str.back());
        }
        string upper = "";
        return gogogo(bottom, upper, 0);
    }
    
    bool gogogo(string bottom, string upper, int pos){
        if(pos == bottom.size()-1){
            if(upper.size() == 1) return true;
            bottom = upper;
            upper = "";
            pos = 0;
        }
        vector<char>& vc= mp[bottom.substr(pos, 2)];
        if(vc.empty()) return false;
        else{
            for(int i = 0; i < vc.size(); i++){
                if(gogogo(bottom, upper + vc[i], pos+1)) return true;
            }
        }
        return false;
    }
};

给你一个 m * n 的矩阵 grid，矩阵中的元素无论是按行还是按列，都以非严格递减顺序排列。 请你统计并返回 grid 中 负数 的数目。

 

示例 1：

输入：grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]
输出：8
解释：矩阵中共有 8 个负数。

示例 2：

输入：grid = [[3,2],[1,0]]
输出：0

 

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 100
• -100 <= grid[i][j] <= 100

 

进阶：你可以设计一个时间复杂度为 O(n + m) 的解决方案吗？

{:width=600px}

注：也可以从左下角开始，方法类似。

总结：利用 $\textit{grid}$ 行列有序的性质，我们可以用 $\mathcal{O}(1)$ 的时间获取 $\mathcal{O}(m)$ 或 $\mathcal{O}(n)$ 的信息。相比之下，$\mathcal{O}(mn)$ 的暴力查找（一个一个地找），每次花费 $\mathcal{O}(1)$ 的时间，只获取了 $\mathcal{O}(1)$ 的信息。

这就是为什么我们可以把 $\mathcal{O}(mn)$ 的暴力查找优化成 $\mathcal{O}(m+n)$。

###py

class Solution:
    def countNegatives(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        ans = 0
        i, j = 0, n - 1  # 从右上角开始
        while i < m and j >= 0:  # 还有剩余元素
            if grid[i][j] < 0:
                ans += m - i  # 这一列剩余元素都是负数
                j -= 1
            else:
                i += 1  # 这一行剩余元素全都非负，排除
        return ans

###java

class Solution {
    public int countNegatives(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int ans = 0;
        int i = 0;
        int j = n - 1; // 从右上角开始
        while (i < m && j >= 0) { // 还有剩余元素
            if (grid[i][j] < 0) {
                ans += m - i; // 这一列剩余元素都是负数
                j--;
            } else {
                i++; // 这一行剩余元素全都非负，排除
            }
        }
        return ans;
    }
}

###cpp

class Solution {
public:
    int countNegatives(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        int ans = 0;
        int i = 0, j = n - 1; // 从右上角开始
        while (i < m && j >= 0) { // 还有剩余元素
            if (grid[i][j] < 0) {
                ans += m - i; // 这一列剩余元素都是负数
                j--;
            } else {
                i++; // 这一行剩余元素全都非负，排除
            }
        }
        return ans;
    }
};

###c

int countNegatives(int** grid, int gridSize, int* gridColSize) {
    int m = gridSize, n = gridColSize[0];
    int ans = 0;
    int i = 0, j = n - 1; // 从右上角开始
    while (i < m && j >= 0) { // 还有剩余元素
        if (grid[i][j] < 0) {
            ans += m - i; // 这一列剩余元素都是负数
            j--;
        } else {
            i++; // 这一行剩余元素全都非负，排除
        }
    }
    return ans;
}

###go

func countNegatives(grid [][]int) (ans int) {
m, n := len(grid), len(grid[0])
i, j := 0, n-1 // 从右上角开始
for i < m && j >= 0 { // 还有剩余元素
if grid[i][j] < 0 {
ans += m - i // 这一列剩余元素都是负数
j--
} else {
i++ // 这一行剩余元素全都非负，排除
}
}
return
}

###js

var countNegatives = function(grid) {
    const m = grid.length, n = grid[0].length;
    let ans = 0;
    let i = 0, j = n - 1; // 从右上角开始
    while (i < m && j >= 0) { // 还有剩余元素
        if (grid[i][j] < 0) {
            ans += m - i; // 这一列剩余元素都是负数
            j--;
        } else {
            i++; // 这一行剩余元素全都非负，排除
        }
    }
    return ans;
};

###rust

impl Solution {
    pub fn count_negatives(grid: Vec<Vec<i32>>) -> i32 {
        let m = grid.len();
        let n = grid[0].len();
        let mut ans = 0;
        let mut i = 0;
        let mut j = n - 1; // 从右上角开始
        while i < m && j < n { // 还有剩余元素
            if grid[i][j] < 0 {
                ans += m - i; // 这一列剩余元素都是负数
                j -= 1;
            } else {
                i += 1; // 这一行剩余元素全都非负，排除
            }
        }
        ans as _
    }
}

复杂度分析

• 时间复杂度：$\mathcal{O}(m + n)$，其中 $m$ 和 $n$ 分别是 $\textit{grid}$ 的行数和列数。
• 空间复杂度：$\mathcal{O}(1)$。

注：本题不存在时间复杂度低于 $\mathcal{O}(m + n)$ 的算法，见 240 题我的题解 文末的注。

相似题目

240. 搜索二维矩阵 II

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

解题思路

第一种：全部遍历，没什么技巧。
第二种：从右上到左下下梯子。

代码

第一种：

class Solution:
    def countNegatives(self, grid: List[List[int]]) -> int:
        total = 0
        for item in grid:
            for num in item:
                if num < 0 :
                    total += 1
        
        return total
            

第二种：

class Solution:
    def countNegatives(self, grid: List[List[int]]) -> int:
        total = 0
        i, j = 0, len(grid[0])-1

        while i < len(grid) and j>=0:
            if grid[i][j] >= 0:
                i += 1
            else:
                total += len(grid) - i
                j -= 1
        return total

方法一：暴力

观察数据范围注意到矩阵大小不会超过 $100*100=10^4$，所以我们可以遍历矩阵所有数，统计负数的个数。

###C++

class Solution {
public:
    int countNegatives(vector<vector<int>>& grid) {
        int num = 0;
        for (int x : grid) {
            for (int y : x) {
                if (y < 0) {
                    num++;
                }
            }
        }
        return num;
    }
};

###Java

class Solution {
    public int countNegatives(int[][] grid) {
        int num = 0;
        for (int[] row : grid) {
            for (int value : row) {
                if (value < 0) {
                    num++;
                }
            }
        }
        return num;
    }
}

###C#

public class Solution {
    public int CountNegatives(int[][] grid) {
        int num = 0;
        foreach (int[] row in grid) {
            foreach (int value in row) {
                if (value < 0) {
                    num++;
                }
            }
        }
        return num;
    }
}

###Go

func countNegatives(grid [][]int) int {
    num := 0
    for _, row := range grid {
        for _, value := range row {
            if value < 0 {
                num++
            }
        }
    }
    return num
}

###Python

class Solution:
    def countNegatives(self, grid: List[List[int]]) -> int:
        num = 0
        for row in grid:
            for value in row:
                if value < 0:
                    num += 1
        return num

###C

int countNegatives(int** grid, int gridSize, int* gridColSize) {
    int num = 0;
    for (int i = 0; i < gridSize; i++) {
        for (int j = 0; j < gridColSize[i]; j++) {
            if (grid[i][j] < 0) {
                num++;
            }
        }
    }
    return num;
}

###JavaScript

var countNegatives = function(grid) {
    let num = 0;
    for (const row of grid) {
        for (const value of row) {
            if (value < 0) {
                num++;
            }
        }
    }
    return num;
};

###TypeScript

function countNegatives(grid: number[][]): number {
    let num = 0;
    for (const row of grid) {
        for (const value of row) {
            if (value < 0) {
                num++;
            }
        }
    }
    return num;
};

###Rust

impl Solution {
    pub fn count_negatives(grid: Vec<Vec<i32>>) -> i32 {
        let mut num = 0;
        for row in grid {
            for value in row {
                if value < 0 {
                    num += 1;
                }
            }
        }
        num
    }
}

复杂度分析

• 时间复杂度：$O(nm)$，即矩阵元素的总个数。
• 空间复杂度：$O(1)$。

方法二：二分查找

注意到题目中给了一个性质，即矩阵中的元素无论是按行还是按列，都以非递增顺序排列，可以考虑把这个性质利用起来优化暴力。已知这个性质告诉了我们每一行的数都是有序的，所以我们通过二分查找可以找到每一行中从前往后的第一个负数，那么这个位置之后到这一行的末尾里所有的数必然是负数了，可以直接统计。

1. 遍历矩阵的每一行。

2. 二分查找到该行从前往后的第一个负数，考虑第 $i$ 行，我们记这个位置为 $pos_i$，那么第 $i$ 行 $[pos_i,m-1]$ 中的所有数都是负数，所以这一行对答案的贡献就是 $m-1-pos_i+1=m-pos_i$。

3. 最后的答案就是 $\sum_{i=0}^{n-1}(m-pos_i)$。

###C++

class Solution {
public:
    int countNegatives(vector<vector<int>>& grid) {
        int num = 0;
        for (auto x : grid) {
            int l = 0, r = (int)x.size() - 1, pos = -1;
            while (l <= r) {
                int mid = l + ((r - l) >> 1);
                if (x[mid] < 0) {
                    pos = mid;
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            }
            
            if (~pos) {  // pos != -1 表示这一行存在负数
                num += (int)x.size() - pos;
            }
        }
        return num;
    }
};

###Java

class Solution {
    public int countNegatives(int[][] grid) {
        int num = 0;
        for (int[] row : grid) {
            int l = 0, r = row.length - 1, pos = -1;
            while (l <= r) {
                int mid = l + (r - l) / 2;
                if (row[mid] < 0) {
                    pos = mid;
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            }
            if (pos != -1) {
                num += row.length - pos;
            }
        }
        return num;
    }
}

###C#

public class Solution {
    public int CountNegatives(int[][] grid) {
        int num = 0;
        foreach (int[] row in grid) {
            int l = 0, r = row.Length - 1, pos = -1;
            while (l <= r) {
                int mid = l + (r - l) / 2;
                if (row[mid] < 0) {
                    pos = mid;
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            }
            if (pos != -1) {
                num += row.Length - pos;
            }
        }
        return num;
    }
}

###Go

func countNegatives(grid [][]int) int {
    num := 0
    for _, row := range grid {
        l, r, pos := 0, len(row) - 1, -1
        for l <= r {
            mid := l + (r - l) / 2
            if row[mid] < 0 {
                pos = mid
                r = mid - 1
            } else {
                l = mid + 1
            }
        }
        if pos != -1 {
            num += len(row) - pos
        }
    }
    return num
}

###Python

class Solution:
    def countNegatives(self, grid: List[List[int]]) -> int:
        num = 0
        for row in grid:
            l, r, pos = 0, len(row) - 1, -1
            while l <= r:
                mid = l + (r - l) // 2
                if row[mid] < 0:
                    pos = mid
                    r = mid - 1
                else:
                    l = mid + 1
            if pos != -1:
                num += len(row) - pos
        return num

###C

int countNegatives(int** grid, int gridSize, int* gridColSize) {
    int num = 0;
    for (int i = 0; i < gridSize; i++) {
        int l = 0, r = gridColSize[i] - 1, pos = -1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (grid[i][mid] < 0) {
                pos = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        if (pos != -1) {
            num += gridColSize[i] - pos;
        }
    }
    return num;
}

###JavaScript

var countNegatives = function(grid) {
    let num = 0;
    for (const row of grid) {
        let l = 0, r = row.length - 1, pos = -1;
        while (l <= r) {
            const mid = l + Math.floor((r - l) / 2);
            if (row[mid] < 0) {
                pos = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        if (pos !== -1) {
            num += row.length - pos;
        }
    }
    return num;
};

###TypeScript

function countNegatives(grid: number[][]): number {
    let num = 0;
    for (const row of grid) {
        let l = 0, r = row.length - 1, pos = -1;
        while (l <= r) {
            const mid = l + Math.floor((r - l) / 2);
            if (row[mid] < 0) {
                pos = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        if (pos !== -1) {
            num += row.length - pos;
        }
    }
    return num;
}

###Rust

impl Solution {
    pub fn count_negatives(grid: Vec<Vec<i32>>) -> i32 {
        let mut num = 0;
        for row in grid {
            let (mut l, mut r, mut pos) = (0, row.len() as i32 - 1, -1);
            while l <= r {
                let mid = l + (r - l) / 2;
                if row[mid as usize] < 0 {
                    pos = mid;
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            }
            if pos != -1 {
                num += row.len() as i32 - pos;
            }
        }
        num
    }
}

复杂度分析

• 时间复杂度：二分查找一行的时间复杂度为$logm$，需要遍历$n$行，所以总时间复杂度是$O(nlogm)$。
• 空间复杂度：$O(1)$。

方法三：分治

方法二其实只利用了一部分的性质，即每一行是非递增的，但其实整个矩阵是每行每列均非递增，这说明了一个更重要的性质：每一行从前往后第一个负数的位置是不断递减的，即我们设第 $i$ 行的第一个负数的位置为 $pos_i$，不失一般性，我们把一行全是正数的 $pos$ 设为 $m$，则
$$
pos_0>=pos_1>=pos_2>=...>=pos_{n-1}
$$
所以我们可以依此设计一个分治算法。

我们设计一个函数 $solve(l,r,L,R)$ 表示我们在统计 $[l,r]$ 行的答案，第 $[l,r]$ 行 $pos$ 的位置在 $[L,R]$ 列中，计算 $[l,r]$ 的中间行第 $mid$ 行的的 $pos_{mid}$，算完以后根据之前的方法计算这一行对答案的贡献。然后根据我们之前发现的性质，可以知道 $[l,mid-1]$ 中所有行的 $pos$ 是大于等于 $pos_{mid}$，$[mid+1,r]$ 中所有行的 $pos$ 值是小于等于 $pos_{mid}$ 的，所以可以分成两部分递归下去，即：
$$
solve(l,mid-1,pos_{mid},R)
$$
和
$$
solve(mid+1,r,L,pos_{mid})
$$
所以答案就是 $m-pos_{mid}+solve(l,mid-1,pos_{mid},R)+solve(mid+1,r,L,pos_{mid})$。

递归函数入口为 $solve(0,n-1,0,m-1)$。

###C++

class Solution {
public:
    int solve(int l, int r, int L, int R, vector<vector<int>>& grid) {
        if (l > r) {
            return 0;
        }
        
        int mid = l + ((r - l) >> 1);
        int pos = -1;
        // 在当前行中查找第一个负数
        for (int i = L; i <= R; ++i) {
            if (grid[mid][i] < 0) {
                pos = i;
                break;
            }
        }
        int ans = 0;
        if (pos != -1) {
            // 当前行找到负数，计算当前行的负数个数
            ans += (int)grid[0].size() - pos;
            // 递归处理上半部分（使用更小的列范围）
            ans += solve(l, mid - 1, pos, R, grid);
            // 递归处理下半部分（使用相同的列起始范围）
            ans += solve(mid + 1, r, L, pos, grid);
        } else {
            // 当前行没有负数，只需要递归处理下半部分
            ans += solve(mid + 1, r, L, R, grid);
        }
        
        return ans;
    }
    
    int countNegatives(vector<vector<int>>& grid) {
        return solve(0, (int)grid.size() - 1, 0, (int)grid[0].size() - 1, grid);
    }
};  

###Java

class Solution {
    private int solve(int l, int r, int L, int R, int[][] grid) {
        if (l > r) {
            return 0;
        }
        
        int mid = l + (r - l) / 2;
        int pos = -1;
        // 在当前行中查找第一个负数
        for (int i = L; i <= R; i++) {
            if (grid[mid][i] < 0) {
                pos = i;
                break;
            }
        }
        
        int ans = 0;
        if (pos != -1) {
            // 当前行找到负数，计算当前行的负数个数
            ans += grid[0].length - pos;
            // 递归处理上半部分（使用更小的列范围）
            ans += solve(l, mid - 1, pos, R, grid);
            // 递归处理下半部分（使用相同的列起始范围）
            ans += solve(mid + 1, r, L, pos, grid);
        } else {
            // 当前行没有负数，只需要递归处理下半部分
            ans += solve(mid + 1, r, L, R, grid);
        }
        return ans;
    }
    
    public int countNegatives(int[][] grid) {
        return solve(0, grid.length - 1, 0, grid[0].length - 1, grid);
    }
}

###C#

public class Solution {
    private int Solve(int l, int r, int L, int R, int[][] grid) {
        if (l > r) {
            return 0;
        }
        
        int mid = l + (r - l) / 2;
        int pos = -1;
        // 在当前行中查找第一个负数
        for (int i = L; i <= R; i++) {
            if (grid[mid][i] < 0) {
                pos = i;
                break;
            }
        }
        int ans = 0;
        if (pos != -1) {
            // 当前行找到负数，计算当前行的负数个数
            ans += grid[0].Length - pos;
            // 递归处理上半部分（使用更小的列范围）
            ans += Solve(l, mid - 1, pos, R, grid);
            // 递归处理下半部分（使用相同的列起始范围）
            ans += Solve(mid + 1, r, L, pos, grid);
        } else {
            // 当前行没有负数，只需要递归处理下半部分
            ans += Solve(mid + 1, r, L, R, grid);
        }
        
        return ans;
    }
    
    public int CountNegatives(int[][] grid) {
        return Solve(0, grid.Length - 1, 0, grid[0].Length - 1, grid);
    }
}

###Go

func countNegatives(grid [][]int) int {
    var solve func(l, r, L, R int) int
    solve = func(l, r, L, R int) int {
        if l > r {
            return 0
        }
        
        mid := l + (r - l) / 2
        pos := -1
        // 在当前行中查找第一个负数
        for i := L; i <= R; i++ {
            if grid[mid][i] < 0 {
                pos = i
                break
            }
        }
        
        ans := 0
        if pos != -1 {
            // 当前行找到负数，计算当前行的负数个数
            ans += len(grid[0]) - pos
            // 递归处理上半部分（使用更小的列范围）
            ans += solve(l, mid-1, pos, R)
            // 递归处理下半部分（使用相同的列起始范围）
            ans += solve(mid+1, r, L, pos)
        } else {
            // 当前行没有负数，只需要递归处理下半部分
            ans += solve(mid+1, r, L, R)
        }
        
        return ans
    }
    
    return solve(0, len(grid)-1, 0, len(grid[0])-1)
}

###Python

class Solution:
    def countNegatives(self, grid: List[List[int]]) -> int:
        def solve(l: int, r: int, L: int, R: int) -> int:
            if l > r:
                return 0
            mid = l + (r - l) // 2
            pos = -1
            # 在当前行中查找第一个负数
            for i in range(L, R + 1):
                if grid[mid][i] < 0:
                    pos = i
                    break
            ans = 0
            if pos != -1:
                # 当前行找到负数，计算当前行的负数个数
                ans += len(grid[0]) - pos
                # 递归处理上半部分（使用更小的列范围）
                ans += solve(l, mid - 1, pos, R)
                # 递归处理下半部分（使用相同的列起始范围）
                ans += solve(mid + 1, r, L, pos)
            else:
                # 当前行没有负数，只需要递归处理下半部分
                ans += solve(mid + 1, r, L, R)

            return ans
            
        return solve(0, len(grid) - 1, 0, len(grid[0]) - 1)

###C

int solve(int l, int r, int L, int R, int** grid, int gridSize, int gridColSize) {
    if (l > r) {
        return 0;
    }
    
    int mid = l + (r - l) / 2;
    int pos = -1;
    // 在当前行中查找第一个负数
    for (int i = L; i <= R; i++) {
        if (grid[mid][i] < 0) {
            pos = i;
            break;
        }
    }
    
    int ans = 0;
    if (pos != -1) {
        // 当前行找到负数，计算当前行的负数个数
        ans += gridColSize - pos;
        // 递归处理上半部分（使用更小的列范围）
        ans += solve(l, mid - 1, pos, R, grid, gridSize, gridColSize);
        // 递归处理下半部分（使用相同的列起始范围）
        ans += solve(mid + 1, r, L, pos, grid, gridSize, gridColSize);
    } else {
        // 当前行没有负数，只需要递归处理下半部分
        ans += solve(mid + 1, r, L, R, grid, gridSize, gridColSize);
    }
    
    return ans;
}

int countNegatives(int** grid, int gridSize, int* gridColSize) {
    return solve(0, gridSize - 1, 0, gridColSize[0] - 1, grid, gridSize, gridColSize[0]);
}

###JavaScript

var countNegatives = function(grid) {
    const solve = (l, r, L, R) => {
        if (l > r) {
            return 0;
        }
        
        const mid = l + Math.floor((r - l) / 2);
        let pos = -1;
        // 在当前行中查找第一个负数
        for (let i = L; i <= R; i++) {
            if (grid[mid][i] < 0) {
                pos = i;
                break;
            }
        }
        
        let ans = 0;
        if (pos !== -1) {
            // 当前行找到负数，计算当前行的负数个数
            ans += grid[0].length - pos;
            // 递归处理上半部分（使用更小的列范围）
            ans += solve(l, mid - 1, pos, R);
            // 递归处理下半部分（使用相同的列起始范围）
            ans += solve(mid + 1, r, L, pos);
        } else {
            // 当前行没有负数，只需要递归处理下半部分
            ans += solve(mid + 1, r, L, R);
        }
        
        return ans;
    };
    
    return solve(0, grid.length - 1, 0, grid[0].length - 1);
};

###TypeScript

function countNegatives(grid: number[][]): number {
    const solve = (l: number, r: number, L: number, R: number): number => {
        if (l > r) {
            return 0;
        }
        
        const mid = l + Math.floor((r - l) / 2);
        let pos = -1;
        // 在当前行中查找第一个负数
        for (let i = L; i <= R; i++) {
            if (grid[mid][i] < 0) {
                pos = i;
                break;
            }
        }
        
        let ans = 0;
        if (pos !== -1) {
            // 当前行找到负数，计算当前行的负数个数
            ans += grid[0].length - pos;
            // 递归处理上半部分（使用更小的列范围）
            ans += solve(l, mid - 1, pos, R);
            // 递归处理下半部分（使用相同的列起始范围）
            ans += solve(mid + 1, r, L, pos);
        } else {
            // 当前行没有负数，只需要递归处理下半部分
            ans += solve(mid + 1, r, L, R);
        }
        
        return ans;
    };
    
    return solve(0, grid.length - 1, 0, grid[0].length - 1);
}

###Rust

impl Solution {
    pub fn count_negatives(grid: Vec<Vec<i32>>) -> i32 {
        fn solve(l: i32, r: i32, L: i32, R: i32, grid: &Vec<Vec<i32>>) -> i32 {
            if l > r {
                return 0;
            }
            
            let mid = l + (r - l) / 2;
            let mut pos = -1;
            // 在当前行中查找第一个负数
            for i in L..=R {
                if grid[mid as usize][i as usize] < 0 {
                    pos = i;
                    break;
                }
            }
            
            let mut ans = 0;
            if pos != -1 {
                // 当前行找到负数，计算当前行的负数个数
                ans += grid[0].len() as i32 - pos;
                // 递归处理上半部分（使用更小的列范围）
                ans += solve(l, mid - 1, pos, R, grid);
                // 递归处理下半部分（使用相同的列起始范围）
                ans += solve(mid + 1, r, L, pos, grid);
            } else {
                // 当前行没有负数，只需要递归处理下半部分
                ans += solve(mid + 1, r, L, R, grid);
            }
            
            ans
        }
        
        solve(0, grid.len() as i32 - 1, 0, grid[0].len() as i32 - 1, &grid)
    }
}

复杂度分析

• 时间复杂度：代码中找第一个负数的位置是直接遍历 $[L,R]$ 找的，再考虑到 $n$ 和 $m$ 同阶，所以每个 $solve$ 函数里需要消耗 $O(n)$ 的时间，由主定理可得时间复杂度为：
  $$
  T(n)=2T(n/2)+O(n)=O(nlogn)
  $$

• 空间复杂度：$O(1)$。

方法四：倒序遍历

考虑方法三发现的性质，我们可以设计一个更简单的方法。考虑我们已经算出第 $i$ 行的从前往后第一个负数的位置 $pos_i$，那么第 $i+1$ 行的时候，$pos_{i+1}$ 的位置肯定是位于 $[0,pos_i]$ 中，所以对于第 $i+1$ 行我们倒着从 $pos_i$ 循环找 $pos_{i+1}$ 即可，这个循环起始变量是一直在递减的。

###C++

class Solution {
public:
    int countNegatives(vector<vector<int>>& grid) {
        int num = 0;
        int m = (int)grid[0].size();
        int pos = (int)grid[0].size() - 1;
        
        for (auto& row : grid) {
            int i;
            for (i = pos; i >= 0; --i) {
                if (row[i] >= 0) {
                    if (i + 1 < m) {
                        pos = i + 1;
                        num += m - pos;
                    }
                    break;
                }
            }
            if (i == -1) {
                num += m;
                pos = -1;
            }
        }
        
        return num;
    }
};

###Java

class Solution {
    public int countNegatives(int[][] grid) {
        int num = 0;
        int m = grid[0].length;
        int pos = grid[0].length - 1;
        
        for (int[] row : grid) {
            int i;
            for (i = pos; i >= 0; i--) {
                if (row[i] >= 0) {
                    if (i + 1 < m) {
                        pos = i + 1;
                        num += m - pos;
                    }
                    break;
                }
            }
            if (i == -1) {
                num += m;
                pos = -1;
            }
        }
        
        return num;
    }
}

###C#

public class Solution {
    public int CountNegatives(int[][] grid) {
        int num = 0;
        int m = grid[0].Length;
        int pos = grid[0].Length - 1;
        
        foreach (int[] row in grid) {
            int i;
            for (i = pos; i >= 0; i--) {
                if (row[i] >= 0) {
                    if (i + 1 < m) {
                        pos = i + 1;
                        num += m - pos;
                    }
                    break;
                }
            }
            if (i == -1) {
                num += m;
                pos = -1;
            }
        }
        
        return num;
    }
}

###Go

func countNegatives(grid [][]int) int {
    num := 0
    m := len(grid[0])
    pos := len(grid[0]) - 1
    
    for _, row := range grid {
        i := pos
        for ; i >= 0; i-- {
            if row[i] >= 0 {
                if i + 1 < m {
                    pos = i + 1
                    num += m - pos
                }
                break
            }
        }
        if i == -1 {
            num += m
            pos = -1
        }
    }
    
    return num
}

###Python

class Solution:
    def countNegatives(self, grid: List[List[int]]) -> int:
        num = 0
        m = len(grid[0])
        pos = len(grid[0]) - 1
        
        for row in grid:
            i = pos
            while i >= 0:
                if row[i] >= 0:
                    if i + 1 < m:
                        pos = i + 1
                        num += m - pos
                    break
                i -= 1
            if i == -1:
                num += m
                pos = -1
        
        return num

###C

int countNegatives(int** grid, int gridSize, int* gridColSize) {
    int num = 0;
    int m = gridColSize[0];
    int pos = gridColSize[0] - 1;
    
    for (int i = 0; i < gridSize; i++) {
        int j;
        for (j = pos; j >= 0; j--) {
            if (grid[i][j] >= 0) {
                if (j + 1 < m) {
                    pos = j + 1;
                    num += m - pos;
                }
                break;
            }
        }
        if (j == -1) {
            num += m;
            pos = -1;
        }
    }
    
    return num;
}

###JavaScript

var countNegatives = function(grid) {
    let num = 0;
    const m = grid[0].length;
    let pos = grid[0].length - 1;
    
    for (const row of grid) {
        let i;
        for (i = pos; i >= 0; i--) {
            if (row[i] >= 0) {
                if (i + 1 < m) {
                    pos = i + 1;
                    num += m - pos;
                }
                break;
            }
        }
        if (i === -1) {
            num += m;
            pos = -1;
        }
    }
    
    return num;
};

###TypeScript

function countNegatives(grid: number[][]): number {
    let num = 0;
    const m = grid[0].length;
    let pos = grid[0].length - 1;
    
    for (const row of grid) {
        let i: number;
        for (i = pos; i >= 0; i--) {
            if (row[i] >= 0) {
                if (i + 1 < m) {
                    pos = i + 1;
                    num += m - pos;
                }
                break;
            }
        }
        if (i === -1) {
            num += m;
            pos = -1;
        }
    }
    
    return num;
}

###Rust

impl Solution {
    pub fn count_negatives(grid: Vec<Vec<i32>>) -> i32 {
        let mut num = 0;
        let m = grid[0].len();
        let mut pos = (grid[0].len() - 1) as i32;
        
        for row in grid {
            let mut i = pos;
            while i >= 0 {
                if row[i as usize] >= 0 {
                    if i + 1 < m as i32 {
                        pos = i + 1;
                        num += (m as i32) - pos;
                    }
                    break;
                }
                i -= 1;
            }
            if i == -1 {
                num += m as i32;
                pos = -1;
            }
        }
        
        num
    }
}

复杂度分析

• 时间复杂度：考虑每次循环变量的起始位置是单调不降的，所以起始位置最多移动 $m$ 次，时间复杂度 $O(n+m)$。
• 空间复杂度：$O(1)$。

给你一个整数 n ，共有编号从 0 到 n - 1 的 n 个会议室。

给你一个二维整数数组 meetings ，其中 meetings[i] = [starti, endi] 表示一场会议将会在 半闭 时间区间 [starti, endi) 举办。所有 starti 的值 互不相同 。

会议将会按以下方式分配给会议室：

1. 每场会议都会在未占用且编号 最小 的会议室举办。
2. 如果没有可用的会议室，会议将会延期，直到存在空闲的会议室。延期会议的持续时间和原会议持续时间 相同 。
3. 当会议室处于未占用状态时，将会优先提供给原 开始 时间更早的会议。

返回举办最多次会议的房间 编号 。如果存在多个房间满足此条件，则返回编号 最小 的房间。

半闭区间 [a, b) 是 a 和 b 之间的区间，包括 a 但 不包括 b 。

 

示例 1：

输入：n = 2, meetings = [[0,10],[1,5],[2,7],[3,4]]
输出：0
解释：
- 在时间 0 ，两个会议室都未占用，第一场会议在会议室 0 举办。
- 在时间 1 ，只有会议室 1 未占用，第二场会议在会议室 1 举办。
- 在时间 2 ，两个会议室都被占用，第三场会议延期举办。
- 在时间 3 ，两个会议室都被占用，第四场会议延期举办。
- 在时间 5 ，会议室 1 的会议结束。第三场会议在会议室 1 举办，时间周期为 [5,10) 。
- 在时间 10 ，两个会议室的会议都结束。第四场会议在会议室 0 举办，时间周期为 [10,11) 。
会议室 0 和会议室 1 都举办了 2 场会议，所以返回 0 。 

示例 2：

输入：n = 3, meetings = [[1,20],[2,10],[3,5],[4,9],[6,8]]
输出：1
解释：
- 在时间 1 ，所有三个会议室都未占用，第一场会议在会议室 0 举办。
- 在时间 2 ，会议室 1 和 2 未占用，第二场会议在会议室 1 举办。
- 在时间 3 ，只有会议室 2 未占用，第三场会议在会议室 2 举办。
- 在时间 4 ，所有三个会议室都被占用，第四场会议延期举办。 
- 在时间 5 ，会议室 2 的会议结束。第四场会议在会议室 2 举办，时间周期为 [5,10) 。
- 在时间 6 ，所有三个会议室都被占用，第五场会议延期举办。 
- 在时间 10 ，会议室 1 和 2 的会议结束。第五场会议在会议室 1 举办，时间周期为 [10,12) 。 
会议室 1 和会议室 2 都举办了 2 场会议，所以返回 1 。 

 

提示：

• 1 <= n <= 100
• 1 <= meetings.length <= 105
• meetings[i].length == 2
• 0 <= starti < endi <= 5 * 105
• starti 的所有值 互不相同

由于 $n\le 100$，可以直接按照题目模拟：

1. 按开始时间排序，依次安排 meetings

2. 维护每个会议室的 最早可用时间 $t$。每次安排会议$[start, end)$时，将那些 $t$ 早于 $start$ 的会议室的 $t$ 设为 $start$。这样处理后只需从中选择 $t$ 最早的会议室即可（如果有相等的选下标最小的）。

3. 同时维护 $cnt$ 数组，遍历完成后按要求返回答案即可

###python

class Solution:
    def mostBooked(self, n: int, meetings: List[List[int]]) -> int:
        cnt, t = [0] * n, [0] * n
        
        for [s, e] in sorted(meetings):
            t = list(map(lambda x : max(x, s), t))
            choice = t.index(min(t))
            t[choice], cnt[choice] = t[choice] + e - s, cnt[choice] + 1
            
        return cnt.index(max(cnt))

按照时间顺序模拟开会过程。

对于会议 $[\textit{start},\textit{end})$，我们需要知道：

• 在 $\textit{start}$ 时刻空闲的会议室中，编号最小的会议室。可以用一个最小堆 $\textit{idle}$ 维护空闲会议室的编号。
• 如果没有空闲的会议室呢？我们需要找最早结束的会议室。可以用一个最小堆 $\textit{using}$ 维护使用中的会议室的结束时间和编号。

这两类会议室是互补关系，伴随着会议的开始和结束，会议室在这两类中来回倒：

• 首先，从 $\textit{using}$ 中去掉结束时间小于等于 $\textit{start}$ 的所有会议室，将其编号添加到 $\textit{idle}$ 中。
• 然后分类讨论：
  • 如果此时有空闲的会议室，那么从 $\textit{idle}$ 中弹出编号最小的会议室，和 $\textit{end}$ 一起，添加到 $\textit{using}$ 中。
  • 否则，从 $\textit{using}$ 中弹出一个最早结束的会议室（若有多个同时结束，弹出编号最小的会议室），设其结束时间为 $e$，则我们等待了 $e-\textit{start}$ 时间，所以当前会议的结束时间为 $\textit{end} + e-\textit{start}$。

在上述模拟的过程中，每使用一个编号为 $i$ 的会议室，就把 $i$ 的出现次数加一。最后返回出现次数最大的编号（如果有多个编号的出现次数相同，返回其中最小的编号）。

注意题目保证所有会议的开始时间互不相同。

class Solution:
    def mostBooked(self, n: int, meetings: List[List[int]]) -> int:
        meetings.sort(key=lambda m: m[0])

        idle = list(range(n))  # 会议室编号
        using = []  # (结束时间，会议室编号)
        cnt = [0] * n  # 会议室的开会次数

        for start, end in meetings:
            # 在 start 时刻空出来的会议室
            while using and using[0][0] <= start:
                heappush(idle, heappop(using)[1])

            if idle:  # 有空闲的会议室
                i = heappop(idle)
            else:  # 没有空闲的会议室
                e, i = heappop(using)  # 弹出一个最早结束的会议室（若有多个同时结束，弹出编号最小的会议室）
                end += e - start  # 更新当前会议的结束时间

            heappush(using, (end, i))  # 使用一个会议室
            cnt[i] += 1

        return cnt.index(max(cnt))

class Solution {
    public int mostBooked(int n, int[][] meetings) {
        Arrays.sort(meetings, (a, b) -> a[0] - b[0]);

        PriorityQueue<Integer> idle = new PriorityQueue<>(); // 会议室编号
        for (int i = 0; i < n; i++) {
            idle.offer(i);
        }
        PriorityQueue<long[]> using = new PriorityQueue<>(
            (a, b) -> a[0] != b[0] ? Long.compare(a[0], b[0]) : Long.compare(a[1], b[1])
        ); // (结束时间，会议室编号)
        int[] cnt = new int[n]; // 会议室的开会次数

        for (int[] m : meetings) {
            long start = m[0];
            long end = m[1];

            // 在 start 时刻空出来的会议室
            while (!using.isEmpty() && using.peek()[0] <= start) {
                idle.offer((int) using.poll()[1]);
            }

            int i;
            if (!idle.isEmpty()) { // 有空闲的会议室
                i = idle.poll();
            } else { // 没有空闲的会议室
                long[] p = using.poll(); // 弹出一个最早结束的会议室（若有多个同时结束，弹出编号最小的会议室）
                end += p[0] - start; // 更新当前会议的结束时间
                i = (int) p[1];
            }

            using.offer(new long[]{end, i}); // 使用一个会议室
            cnt[i]++;
        }

        int ans = 0;
        for (int i = 1; i < n; i++) {
            if (cnt[i] > cnt[ans]) {
                ans = i;
            }
        }
        return ans;
    }
}

class Solution {
public:
    int mostBooked(int n, vector<vector<int>>& meetings) {
        ranges::sort(meetings, {}, [](auto& m) { return m[0]; });

        priority_queue<int, vector<int>, greater<>> idle; // 会议室编号
        for (int i = 0; i < n; i++) {
            idle.push(i);
        }
        priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> using_; // (结束时间，会议室编号)
        vector<int> cnt(n); // 会议室的开会次数

        for (auto& m : meetings) {
            long long start = m[0], end = m[1];

            // 在 start 时刻空出来的会议室
            while (!using_.empty() && using_.top().first <= start) {
                idle.push(using_.top().second);
                using_.pop();
            }

            int i;
            if (!idle.empty()) { // 有空闲的会议室
                i = idle.top();
                idle.pop();
            } else { // 没有空闲的会议室
                // 弹出一个最早结束的会议室（若有多个同时结束，弹出编号最小的会议室）
                auto [e, room] = using_.top();
                i = room;
                using_.pop(); 
                end += e - start; // 更新当前会议的结束时间
            }

            using_.emplace(end, i); // 使用一个会议室
            cnt[i]++;
        }

        return ranges::max_element(cnt) - cnt.begin();
    }
};

func mostBooked(n int, meetings [][]int) (ans int) {
slices.SortFunc(meetings, func(a, b []int) int { return a[0] - b[0] })

idle := hp{make([]int, n)} // 会议室编号
for i := range n {
idle.IntSlice[i] = i
}
using := hp2{} // (结束时间，会议室编号)
cnt := make([]int, n) // 会议室的开会次数

for _, m := range meetings {
start, end := m[0], m[1]

// 在 start 时刻空出来的会议室
for len(using) > 0 && using[0].end <= start {
heap.Push(&idle, heap.Pop(&using).(pair).i)
}

var i int
if idle.Len() > 0 { // 有空闲的会议室
i = heap.Pop(&idle).(int)
} else {
// 弹出一个最早结束的会议室（若有多个同时结束，弹出编号最小的会议室）
p := heap.Pop(&using).(pair)
end += p.end - start // 更新当前会议的结束时间  
i = p.i
}

heap.Push(&using, pair{end, i}) // 使用一个会议室
cnt[i]++
}

for i, c := range cnt {
if c > cnt[ans] {
ans = i
}
}
return
}

type hp struct{ sort.IntSlice }
func (h *hp) Push(v any) { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *hp) Pop() any   { a := h.IntSlice; v := a[len(a)-1]; h.IntSlice = a[:len(a)-1]; return v }

type pair struct{ end, i int }
type hp2 []pair
func (h hp2) Len() int { return len(h) }
func (h hp2) Less(i, j int) bool {
a, b := h[i], h[j]
return a.end < b.end || a.end == b.end && a.i < b.i
}
func (h hp2) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *hp2) Push(v any)   { *h = append(*h, v.(pair)) }
func (h *hp2) Pop() any     { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }

复杂度分析

• 时间复杂度：$\mathcal{O}(m\log m + n + m\log n)$，其中 $m$ 是 $\textit{meetings}$ 的长度。注意每个会议至多入堆出堆各一次。
• 空间复杂度：$\mathcal{O}(n)$。

相似题目

• 1882. 使用服务器处理任务 1979
• 1606. 找到处理最多请求的服务器 2276

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府