class Solution:
  
  def get_neighbors(self, matrix, i, j):
    neighbors = []
    rows = [-1, 0, 1, 0]
    cols = [0, 1, 0, -1]
    for k in range(len(rows)):
      x = rows[k] + i
      y = cols[k] + j
      if x >= 0 and x < len(matrix) and y >= 0 and y < len(matrix[0]):
        neighbors.append((x, y))
    return neighbors
  
  def cacl_perimeter(self, matrix, i, j):
    perimeter = 0
    # top perimeter
    if  i == 0 or (i - 1 >= 0 and matrix[i - 1][j] == 0):
      perimeter += 1
    # bottom perimeter  
    if  i == len(matrix) - 1 or (i + 1 < len(matrix) and matrix[i + 1][j] == 0):
      perimeter += 1
    # left perimeter
    if  j == 0 or (j - 1 >= 0 and matrix[i][j - 1] == 0):
      perimeter += 1
    # right perimeter  
    if  j == len(matrix[0]) - 1 or (j + 1 < len(matrix[0]) and matrix[i][j + 1] == 0):
      perimeter += 1  
    return perimeter

  def dfs(self, matrix, i, j):
    if matrix[i][j] == 0 or matrix[i][j] == 2: # ignore visited or 0
      return 0 
    
    matrix[i][j] = 2 # visited
    result = self.cacl_perimeter(matrix, i, j)
    
    for row, col in self.get_neighbors(matrix, i, j):
      result += self.dfs(matrix, row, col)

    return result

  def findIslandPerimeter(self, matrix):
    for i in range(len(matrix)):
      for j in range(len(matrix[i])):
        perimeters = self.dfs(matrix, i , j)
        if perimeters > 0:
          return perimeters
    return 0