今日题目

https://leetcode.com/problems/maximum-number-of-fish-in-a-grid/description/

思路

求连通块的大小。

方法

遍历网格，将每个连通块中的鱼数累加，最终返回最大连通块的鱼数。

复杂度

  • 时间复杂度：$O(N\times M)$，每个格子恰好访问一次。

  • 空间复杂度：$O(1)$，不计原始网格占用的空间。

代码

class Solution:
    def findMaxFish(self, grid: List[List[int]]) -> int:
        ans = 0
        dx = [0,0,1,-1]
        dy = [1,-1,0,0]
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 0:
                    continue
                tmp = grid[i][j]
                grid[i][j] = 0
                q = deque([(i,j)])
                while len(q) > 0:
                    x,y = q.popleft()
                    for k in range(4):
                        nx = x + dx[k]
                        ny = y + dy[k]
                        if nx < 0 or ny < 0 or nx >= len(grid) or ny >= len(grid[0]) or grid[nx][ny] == 0:
                            continue
                        
                        tmp += grid[nx][ny]
                        grid[nx][ny] = 0
                        # print(i,j,nx, ny, tmp)
                        q.append((nx, ny))
                
                ans = max(ans, tmp)
    
        print(grid)

        return ans