題目:
給你一個由?
'1'
(陸地)和?'0'
(水)組成的的二維網格,請你計算網格中島嶼的數量。島嶼總是被水包圍,并且每座島嶼只能由水平方向和/或豎直方向上相鄰的陸地連接形成。
此外,你可以假設該網格的四條邊均被水包圍。
來源:力扣(LeetCode)
鏈接:力扣(LeetCode)官網 - 全球極客摯愛的技術成長平臺
示例:
示例 1:
輸入:
grid = [["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"] ]
輸出:1
示例 2:輸入:
grid = [["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"] ]
輸出:3
解法:
遍歷每個點,如果為1,計數+1并把周圍相鄰的1標記為2。
代碼:
class Solution:def numIslands(self, grid: List[List[str]]) -> int:count = 0def infect(r, c):if 0 <= r < len(grid) and 0 <= c < len(grid[0]) and grid[r][c] == '1':grid[r][c] = '2'infect(r + 1, c)infect(r - 1, c)infect(r, c + 1)infect(r, c - 1)for idr, r in enumerate(grid):for idc, c in enumerate(r):if c == '1':infect(idr, idc)count += 1return count