題目

解題概念

  • 此題簡單來說，就是要在值為 1 或 0 的陣列中，找出 island的最大面積 (即值為 1 的最大面積)
  • 搜尋的方式 : 我採用雙重 for 迴圈，從 grid[0][0]、grid[0][1]…、grid[1][0]…grid[m][n]
  • 而在實際執行上，我使用 Graph 中的 DFS(Depth-First Search; 深度搜尋)
    • Def :
      • 先選定一個頂點 A 開始走訪
      • 接著從與頂點 A 相鄰 & 未被走過的頂點中，擇一走訪標示為記錄點，以此類推，不斷從新記錄點的相鄰未被走過頂點中尋找
      • 若新紀錄點的相鄰頂點都被走過，則退回前一個紀錄點，繼續從未被走過頂點中尋找

        補充 : DFS 與 BFS 之差異

    • 轉換成此題實際應用 :
      • 先選定左上角的grid[0][0]為起始點
      • 接著從grid[0][0]的上下左右，擇一走訪標示為記錄點，以此類推，不斷從新記錄點的上下左右 & 未被走過之頂點中尋找
      • 若新紀錄點的上下左右都被走過，則退回前一個紀錄點，繼續從未被走過頂點中尋找
      • 標示某點為已探訪的方式 : 將其值調成 0，這樣後續搜尋時就不會有重複計算的問題
  • 此次解題，我是用遞迴的方式去解，但其實也可以用非遞迴的方式，但就需要另外使用 Stack 去操作了

實際寫Code

  • 目標函式 : maxAreaOfIsland(grid)
    • Input : grid: List[List[int]]
    • Output : int
  • 前置作業 : 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    i_len = len(grid) # 取出 Column 的長度
    j_len = len(grid[0]) # 取出 Row 的長度
    max = 0 # 預設最大面積為 0
        
    # def DFS(...):
        # ...
        
    # 針對所有格子跑雙重 for 迴圈
    for i in range(i_len):
        for j in range(j_len):
        
            # 若還有尚未探訪的點
            if grid[i][j] == 1:
                # 透過 DFS() ，將該點的面積存入 temp 中
                temp = DFS(i, j)

            # 若 temp 大於 max，則用 temp 的值取代 max
            if max < temp:
                max = temp    

    # 最終的 max 即為最大面積    
    return max
  • 主要遞迴部分 : 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    # Input : 欲檢查的點，即grid[i][j]
    # Output : 該點延伸出的總面積
    def DFS(i, j):

        # 若 i 與 j 的值在合理範圍，且 grid[i][j] 為 1
        if 0 <= i < i_len and 0 <= j < j_len and grid[i][j]:

            # 將其設為0，代表已探訪過
            grid[i][j] = 0

            # 回傳上下左右格子的面積，再加上自己的面積(= 1)
            return 1 + DFS(i-1, j) + DFS(i+1, j) + DFS(i, j-1) + DFS(i, j+1)

        # 否則就回傳 0
        else:
            return 0

參考資料

  1. 【Day33】[演算法]-深度優先搜尋DFS與廣度優先搜尋BFS