图论 5. 孤岛的总面积

101. 孤岛的总面积

代码随想录

卡码网无难度标识

• 思路：

  无论dfs、bfs思路都差不多

  • 注意孤岛是那些位于矩阵内部、所有单元格都不接触边缘的岛屿。

  • 要计算孤岛面积，其实就是：

    遍历地图的上下左右四条边上的格子，

    如果格子是陆地，那么就通过dfs或者bfs将这些陆地所在的岛屿处的格子全部更新为海洋，也就是修改其值为0，因为这些岛屿都不符合孤岛的要求；

  • 这样graph中剩下仍为1的格子，就一定属于孤岛了，

    直接求和就是孤岛总面积（因此不需要在这一阶段用dfs了）。

  • 因此这样做也就不需要使用访问表了，因为graph的更新（从1变为0）直接可以写在dfs中，并同时充当了访问表的作用

• dfs代码：

  import sys
  def dfs(graph, i, j): # 利用dfs来去除所有和graph上下左右四边沾边的岛屿
      directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
      n = len(graph)
      m = len(graph[0])
      graph[i][j] = 0 # 更新当前格子为0
  
      for di, dj in directions:
          newi = i + di
          newj = j + dj
          if 0 <= newi < n and 0 <= newj < m:
              if graph[newi][newj] == 1: # 说明未访问过
                  dfs(graph, newi, newj)
  
  
  def main():
      lines = sys.stdin.readlines()
      n, m = map(int, lines[0].strip().split()) # 行，列
      graph = [] # 地图
      for i in range(1, len(lines)):
          graph.append(list(map(int, lines[i].strip().split())))
  
      # 注意孤岛是那些位于矩阵内部、所有单元格都不接触边缘的岛屿。
      # 要计算孤岛面积，其实就是：
      # 遍历地图的上下左右四条边上的格子，如果格子是陆地，那么就通过dfs或者bfs将这些陆地所在的岛屿处的格子全部更新为海洋，也就是修改其值为0，因为这些岛屿都不符合孤岛的要求；
      # 这样graph中剩下仍为1的格子，就一定属于孤岛了，直接求和就是孤岛总面积（因此不需要在这一阶段用dfs了）。
      # 因此这样做也就不需要使用访问表了，因为graph的更新（从1变为0）直接可以写在dfs中，并同时充当了访问表的作用
      for i in range(n):
          if graph[i][0] == 1: # 最左列
              dfs(graph, i, 0)
          if graph[i][m-1] == 1: # 最右列
              dfs(graph, i, m-1)
  
      for j in range(m):
          if graph[0][j] == 1: # 最上行
              dfs(graph, 0, j)
          if graph[n-1][j] == 1: # 最下行
              dfs(graph, n-1, j)
  
      res = sum(sum(row) for row in graph) # 计算孤岛面积
      print(res)
  
  if __name__ == '__main__':
      main()
  

• 摘录一个bfs代码，虽然看起来奇奇怪怪的，等以后复习的时候自己再写一个吧

  from collections import deque
  
  # 处理输入
  n, m = list(map(int, input().split()))
  g = []
  for _ in range(n):
      row = list(map(int, input().split()))
      g.append(row)
  
  # 定义四个方向、孤岛面积（遍历完边缘后会被重置）
  directions = [[0,1], [1,0], [-1,0], [0,-1]]
  count = 0
  
  # 广搜
  def bfs(r, c):
      global count
      q = deque()
      q.append((r, c))
      g[r][c] = 0
      count += 1
  
      while q:
          r, c = q.popleft()
          for di in directions:
              next_r = r + di[0]
              next_c = c + di[1]
              if next_c < 0 or next_c >= m or next_r < 0 or next_r >= n:
                  continue
              if g[next_r][next_c] == 1:
                  q.append((next_r, next_c))
                  g[next_r][next_c] = 0
                  count += 1
  
  
  for i in range(n):
      if g[i][0] == 1: 
          bfs(i, 0)
      if g[i][m-1] == 1: 
          bfs(i, m-1)
  
  for i in range(m):
      if g[0][i] == 1: 
          bfs(0, i)
      if g[n-1][i] == 1: 
          bfs(n-1, i)
  
  count = 0
  for i in range(n):
      for j in range(m):
          if g[i][j] == 1: 
              bfs(i, j)
  
  print(count)
  

‍