解法一：暴力法

遍历整张地图，并检测岛屿的上下左右邻居是否存在。

  1. class Solution:
  2.     def islandPerimeter(self, grid: List[List[int]]) -> int:
  3.         ans = 0
  4.         rows, cols = len(grid), len(grid[0])
  5.         for i in range(rows):
  6.             for j in range(cols):
  7.                 if grid[i][j] != 1:
  8.                     continue
  9.                 up = grid[i - 1][j] if i > 0 else 0
  10.                 down = grid[i + 1][j] if i < rows - 1 else 0
  11.                 left = grid[i][j - 1] if j > 0 else 0
  12.                 right = grid[i][j + 1] if j < cols - 1 else 0
  13.                 ans += (4 - up - down - left - right)
  14.         return ans

解法二：暴力法优化

解法一中的相邻岛屿存在重复检查，例如AB相邻，遍历A时检查了B，遍历B时又检查了一次A。利用遍历顺序，因此只需要检查左和上即可。如果当前上无邻居，说明上层的下也无邻居，结果应该额外+1；如果当前的左无邻居，说明左侧的右也无邻居，结果额外+1。综合来看就是每个陆地的左无邻居，结果+2；上无邻居，结果+2。

  1. class Solution:
  2.     def islandPerimeter(self, grid: List[List[int]]) -> int:
  3.         ans = 0
  4.         rows, cols = len(grid), len(grid[0])
  5.         for i in range(rows):
  6.             for j in range(cols):
  7.                 if grid[i][j] != 1:
  8.                     continue
  9.                 ans += not (grid[i - 1][j] if i > 0 else 0) * 2
  10.                 ans += not (grid[i][j - 1] if j > 0 else 0) * 2
  11.         return ans

优化后的运行时间更长了，我表示很无奈…

解法三：深度优先遍历

这样不用暴力遍历整张地图了，但是空间复杂度增加，需要多一个栈。另外第一个节点是需要暴力遍历来发现的…访问过的节点可以通过修改地图值（1改为2）来标记，节省一个visited集合。遍历的时候要检查上下左右邻居。额这个过程是必须的，所以在这一步把ans给累加上就行了。