↓Skip to main content
  1. Posts/

LeetCode-1970 你能穿过矩阵的最后一天

·1 min·
Table of Contents

LeetCode-1970 你能穿过矩阵的最后一天 #

Solution 1 #

如果第 $k$ 天可以, 那么第 $k - 1$ 天也可以. 基于这个性质使用二分查找.

代码如下:

class Solution:
    def latestDayToCross(self, row: int, col: int, cells: List[List[int]]) -> int:
        def check(mid):
            g = [[0 for _ in range(col)] for _ in range(row)]
            vis = g.copy()
            for x, y in cells[:mid + 1]:
                g[x - 1][y - 1] = 1
            q = []
            for i in range(col):
                if g[0][i] == 0:
                    q.append((0, i))
                    vis[0][i] = 1
            while q:
                # print(q)
                nxt_q = []
                for x, y in q:
                    for dx, dy in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
                        nx, ny = x + dx, y + dy
                        if 0 <= nx < row and 0 <= ny < col and vis[nx][ny] == 0 and g[nx][ny] == 0:
                            if nx == row - 1:
                                return True
                            nxt_q.append((nx, ny))
                            vis[nx][ny] = 1
                q = nxt_q.copy()
            return False
                
        l, r = 0, len(cells) - 1
        while l <= r:
            mid = (l + r) // 2
            if check(mid):
                l = mid + 1
            else:
                r = mid - 1
        return (l - 1) + 1