Review list 3

64. Minimum Path Sum

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        if not grid or not grid[0]:return -1
        R, C = len(grid), len(grid[0])
        dp = [[0]*C for _ in range(R)]
        dp[0][0] = grid[0][0]
        for i in range(R):
            for j in range(C):
                if i==0 and j==0:continue
                dp[i][j] += min(dp[i-1][j] if i-1>=0 else float('inf'), dp[i][j-1] if j-1>=0 else float('inf')) + grid[i][j]
        return dp[-1][-1]

74. Search a 2D Matrix

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        if not matrix or not matrix[0] or matrix[-1][-1]<target or matrix[0][0]>target:return False
        R, C = len(matrix), len(matrix[0])
        l, r =0 , R*C-1
        while l<=r:
            m = (l+r)//2
            i, j =m//C, m%C
            if matrix[i][j]==target:return True
            elif matrix[i][j]<target:
                l = m+1
            else:
                r = m-1
        return False

909. Snakes and Ladders

class Solution:
    def snakesAndLadders(self, board: List[List[int]]) -> int:
        if not board or not board[0]:return -1
        R, C = len(board), len(board[0])
        T =R*C
        def bfs():
            Q = collections.deque([(1,0)])
            seen = {1}
            while Q:
                loc, d = Q.popleft()
                if loc == T:return d
                for k in range(1, 7):
                    new_loc = loc+k
                    if new_loc<=T:
                        i, j = (new_loc-1)//C, (new_loc-1)%C
                        if i%2==1: j = C-1-j
                        i = R-1-i
                        if board[i][j]!=-1:
                            new_loc = board[i][j]
                        if new_loc not in seen:
                            seen.add(new_loc)
                            Q.append((new_loc, d+1))
            return -1
        return bfs()