200. Number of Islands
https://leetcode.com/problems/number-of-islands/
題意
給你一個二維的陣列， 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 的筆記本 留言，順手給我個讚吧！你的讚將成為我持續更新的動力，感謝你的閱讀，讓我們一起學習成為更好的自己。