【LeetCode】200. 島嶼的個數

題目

給定一個由?'1'（陸地）和?'0'（水）組成的的二維網格，計算島嶼的數量。一個島被水包圍，并且它是通過水平方向或垂直方向上相鄰的陸地連接而成的。你可以假設網格的四個邊均被水包圍。
示例 1:輸入:

示例?2:輸入:

思路

DFS，深度遍歷搜索
visited記錄遍歷過的陸地

代碼

class Solution:def numIslands(self, grid: List[List[str]]) -> int:if len(grid) == 0:return 0#visited全部初始化為0row, col = len(grid), len(grid[0])visited = [[0 for x in range(0, col)] for y in range(0, row)]count=0for i in range(0,row):for j in range(0,col):if visited[i][j]==0 and grid[i][j]=='1':self.dfs(grid,i,j,visited)count += 1return countdef dfs(self, grid, i, j, visited):if i < 0 or i >= len(grid):returnif j < 0 or j >= len(grid[0]):returnif grid[i][j]=='0' or visited[i][j]==1:returnvisited[i][j] = 1 #遍歷過的地方置為1#上下左右四個方向遍歷self.dfs(grid, i-1, j, visited)self.dfs(grid, i+1, j, visited)self.dfs(grid, i, j-1, visited)self.dfs(grid, i, j+1, visited)

轉載于:https://www.cnblogs.com/wemo/p/10547711.html

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/248349.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/248349.shtml
英文地址，請注明出處：http://en.pswp.cn/news/248349.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！