网格算法练习

本文最后更新于：2023年12月5日下午

记录数组刷题方案。

1267.统计参与通信的服务器

这里有一幅服务器分布图，服务器的位置标识在 m * n 的整数矩阵网格 grid 中，1 表示单元格上有服务器，0 表示没有。

如果两台服务器位于同一行或者同一列，我们就认为它们之间可以进行通信。

请你统计并返回能够与至少一台其他服务器进行通信的服务器的数量。

class Solution:
    def countServers(self, grid: List[List[int]]) -> int:
        if not grid:
            return 0
        row_num = len(grid)
        col_num = len(grid[0])
        if col_num == 0:
            return 0
        
        count_r = [0] * row_num
        count_c = [0] * col_num

        for index_r in range(row_num):
            for index_c in range(col_num):
                if grid[index_r][index_c]:
                    count_r[index_r] += 1
                    count_c[index_c] += 1
        
        total_num = 0
        for index_r in range(row_num):
            for index_c in range(col_num):
                if grid[index_r][index_c] and (count_r[index_r] > 1 or count_c[index_c] > 1):
                    total_num += 1
        return total_num

1293. 网格中的最短路径

给你一个 m * n 的网格，其中每个单元格不是 0（空）就是 1（障碍物）。每一步，您都可以在空白单元格中上、下、左、右移动。

如果您最多可以消除 k 个障碍物，请找出从左上角 (0, 0) 到右下角 (m-1, n-1) 的最短路径，并返回通过该路径所需的步数。如果找不到这样的路径，则返回 -1 。

class Solution:
    def shortestPath(self, grid: List[List[int]], k: int) -> int:
        import numpy as np
        m = len(grid)
        n = len(grid[0])
        if k >= m+n-3:
            return m+n -2
        mark_tensor = np.ones([m, n, k+1]) * 99999
        if grid[0][0]:
            pad_queue = [(0, 0, 0, k-1)]
            mark_tensor[0, 0, 1] = 0
        else:
            pad_queue = [(0, 0, 0, k)]
            mark_tensor[0, 0, 0] = 0
        while pad_queue:
            cur_r, cur_c, cur_step, booms = pad_queue.pop(0)
            for dr, dc in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                next_r = cur_r + dr
                next_c = cur_c + dc
                if 0 <= next_c < n and 0 <= next_r < m:
                    if not grid[next_r][next_c]:
                        if cur_step + 1 < mark_tensor[next_r, next_c, k-booms]:
                            mark_tensor[next_r, next_c, k-booms] = cur_step + 1
                            pad_queue.append((next_r, next_c, cur_step + 1, booms))
                    else:
                        if booms > 0: 
                            cur_booms = booms - 1
                            if cur_step + 1 < mark_tensor[next_r, next_c, k-cur_booms]:
                                mark_tensor[next_r, next_c, k-cur_booms] = cur_step + 1
                                pad_queue.append((next_r, next_c, cur_step + 1, cur_booms))

        min_step_num = mark_tensor[m-1, n-1, :].min()
        if min_step_num > 88888:
            return -1
        else:
            return int(min_step_num)

1091. 二进制矩阵中的最短路径

给你一个 n x n 的二进制矩阵 grid 中，返回矩阵中最短 畅通路径 的长度。如果不存在这样的路径，返回 -1 。

二进制矩阵中的畅通路径是一条从 左上角 单元格（即，(0, 0)）到右下角单元格（即，(n - 1, n - 1)）的路径，该路径同时满足下述要求：

路径途经的所有单元格的值都是 0 。
路径中所有相邻的单元格应当在 8 个方向之一 上连通（即，相邻两单元之间彼此不同且共享一条边或者一个角）。

畅通路径的长度 是该路径途经的单元格总数。

class Solution:
    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
        import numpy as np

        if not grid or grid[0][0] != 0:
            return -1
         
        length = len(grid)
        mark_array = np.array(grid, dtype='int32') * (-1)
        node_queue = [(0, 0, 1)]

        while len(node_queue):

            cur_r, cur_c, step = node_queue.pop(0)
            for d_r in range(-1, 2):
                for d_c in range(-1, 2):
                    neighbor_r, neighbor_c = cur_r + d_r, cur_c + d_c
                    if 0 <= neighbor_r < length and 0 <= neighbor_c < length:
                        if mark_array[neighbor_r, neighbor_c] == 0:
                            node_queue.append((neighbor_r, neighbor_c, step + 1))
                            mark_array[neighbor_r, neighbor_c] = 1
                            if neighbor_r ==length-1 and neighbor_c == length-1:
                                if d_r ==0 and d_c == 0:
                                    return step
                                else:
                                    return step + 1

        return -1

2684. 矩阵中移动的最大次数

给你一个下标从 0 开始、大小为 m x n 的矩阵 grid ，矩阵由若干正整数组成。

你可以从矩阵第一列中的任一单元格出发，按以下方式遍历 grid ：

从单元格 (row, col) 可以移动到 (row - 1, col + 1)、(row, col + 1) 和 (row + 1, col + 1) 三个单元格中任一满足值严格大于当前单元格的单元格。

返回你在矩阵中能够移动的最大次数。

class Solution:
    def maxMoves(self, grid: List[List[int]]) -> int:
        row_num = len(grid)
        col_num = len(grid[0])
        q = set()

        for index in range(row_num):
            q.add((index, 0))
        
        max_step = 0
        while q:
            next_q = set()
            for point in q:
                row, col = point
                cur_value = grid[row][col]
                next_col = col + 1
                if next_col < col_num:
                    for delta in range(-1, 2):
                        next_row = row+delta
                        if next_row < row_num and next_row >= 0:
                            if grid[next_row][next_col] > cur_value:
                                next_q.add((next_row,next_col))
                                if next_col > max_step:
                                    max_step = next_col
            q = next_q
        return max_step

73. 矩阵置零

给定一个 *m* x *n* 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用原地算法**。**

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        remove_row_set = set()
        remove_row_col = set()

        for row_index, row in enumerate(matrix):
            for col_index, value in enumerate(row):
                if value == 0:
                    remove_row_set.add(row_index)
                    remove_row_col.add(col_index)
        
        for row_index, row in enumerate(matrix):
            for col_index, value in enumerate(row):
                if row_index in remove_row_set or col_index in remove_row_col:
                    matrix[row_index][col_index] = 0