200. Number of Islands
https://leetcode.com/problems/number-of-islands/
Medium
Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.
An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example 1:
Input: grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"] ] Output: 1
Example 2:
Input: grid = [ ["1","1","0","0","0"], ["1","1","0","0","0"], ["0","0","1","0","0"], ["0","0","0","1","1"] ] Output: 3
Constraints:
m == grid.lengthn == grid[i].length1 <= m, n <= 300grid[i][j]is'0'or'1'.
題意
給你一個二維的陣列， 1 代表陸地， 0 代表是水，島嶼四面環水，島嶼是由上下左右連接組合而成的，請問這個二維陣列中有幾個島嶼？
解題思路
我們要訪問完全陸地以及水，當遇到陸地就把所有鄰居刷成水，下次再訪問就不會重複計算島嶼了。
- 寫個雙迴圈，要訪問所有的元素。
- 宣告一個 ans 的變數，這個也要當作是結果準備回傳。
- 當遇到 1 ， 將 ans + 1 。
- 將所有相關連再一起的 1 ，把它更新為 0 ，之後再訪問就當作是水處理就好。
- 回傳 ans 。
原始碼
func numIslands(grid [][]byte) int {
if len(grid) == 0 {
return 0
}
m := len(grid)
n := len(grid[0])
ans := 0
for x := 0; x < m; x++ {
for y := 0; y < n; y++ {
if grid[x][y] == '1' {
ans += 1
dfs(grid, x, y, m, n)
}
}
}
return ans
}
func dfs(grid [][]byte, x, y, m, n int) {
if x < 0 || y < 0 || x >= m || y >= n || grid[x][y] == '0' {
return
}
grid[x][y] = '0'
dfs(grid, x + 1, y, m, n)
dfs(grid, x - 1, y, m, n)
dfs(grid, x, y + 1, m, n)
dfs(grid, x, y - 1, m, n)
}
結尾
你有更好或更簡單的解決方案嗎？
歡迎到我的 Facebook Alan 的筆記本 留言，順手給我個讚吧！你的讚將成為我持續更新的動力，感謝你的閱讀，讓我們一起學習成為更好的自己。
