[Leetcode] Max Area of Island 最大島嶼面積
Max Area of Island
最新更新請見:https://yanjia.me/zh/2019/02/...
Given a non-empty 2D array grid of 0's and 1's, an island is a group of 1's (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.
Find the maximum area of an island in the given 2D array. (If there is no island, the maximum area is 0.)
Example 1:
[[0,0,1,0,0,0,0,1,0,0,0,0,0], [0,0,0,0,0,0,0,1,1,1,0,0,0], [0,1,1,0,1,0,0,0,0,0,0,0,0], [0,1,0,0,1,1,0,0,1,0,1,0,0], [0,1,0,0,1,1,0,0,1,1,1,0,0], [0,0,0,0,0,0,0,0,0,0,1,0,0], [0,0,0,0,0,0,0,1,1,1,0,0,0], [0,0,0,0,0,0,0,1,1,0,0,0,0]]
Given the above grid, return 6. Note the answer is not 11, because the island must be connected 4-directionally.
Example 2:
[[0,0,0,0,0,0,0,0]]
Given the above grid, return 0.
Note: The length of each dimension in the given grid does not exceed 50.
深度優先搜尋
思路
該題基本上就是Number of Islands的變形題,唯一的區別是在Number of Islands中我們只需要將搜尋到的陸地置為0,保證其不會再被下次探索所用就行了。但這題多了一要求就是要同時返回島嶼的面積。那麼最簡單的方式就是在遞迴的時候,每個搜尋到的格子都將自身的面積1,加上四個方向搜尋出來的延伸面積都加上,再返回給呼叫遞迴的那個格子作為延伸面積使用,這樣一直返回到島嶼的起始格子時,面積之和就是島嶼的總面積了。
程式碼
Go
func maxAreaOfIsland(grid [][]int) int { maxArea := 0 for i := range grid { for j := range grid[i] { area := measureIsland(grid, i, j) if area > maxArea { maxArea = area } } } return maxArea } func measureIsland(grid [][]int, x, y int) int { if grid[x][y] == 0 { return 0 } area := 1 grid[x][y] = 0 if x > 0 { area += measureIsland(grid, x-1, y) } if x < len(grid)-1 { area += measureIsland(grid, x+1, y) } if y > 0 { area += measureIsland(grid, x, y-1) } if y < len(grid[0])-1 { area += measureIsland(grid, x, y+1) } return area }