• 图可以用邻接表或者邻接矩阵表示
  • 在无权图中找出两个节点最短距离通常用广度优先算法 - 队列实现
  • 在无权图中找出符合条件的路径通常用深度优先算法 - 栈或者递归实现

求最大岛屿面积

链接： https://leetcode.cn/problems/max-area-of-island/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
import queue


class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        lenRows = len(grid)
        lenCols = len(grid[0])
        visited = [[False for _ in range(lenCols)] for _ in range(lenRows)]
        maxArea = 0
        for row in range(lenRows):
            for col in range(lenCols):
                if grid[row][col] == 1 and not visited[row][col]:
                    area = self.getArea(grid, visited, row, col)
                    maxArea = max(maxArea, area)
        return maxArea

    def getArea(self, grid, visited, row, col):
        lenRows = len(grid)
        lenCols = len(grid[0])
        area = 0
        q = queue.Queue()
        q.put((row, col))
        visited[row][col] = True
        directions = [(0, 1), (0, -1), (-1, 0), (1, 0)]
        while not q.empty():
            try:
                area += 1
                curRow, curCol = q.get()
                for dir in directions:
                    nextRow = curRow + dir[0]
                    nextCol = curCol + dir[1]
                    if (
                        0 <= nextRow < lenRows
                        and 0 <= nextCol < lenCols
                        and grid[nextRow][nextCol] == 1
                        and not visited[nextRow][nextCol]
                    ):
                        q.put((nextRow, nextCol))
                        visited[nextRow][nextCol] = True
            except Exception as e:
                break
        return area