Re: [閒聊] 每日leetcode
1905. Count Sub Islands
## 思路
剛看到題目直覺是跑兩次DFS (先標記grid1島編號再檢查grid2)
不過grid2涵蓋多個島的話, 中間一定會碰到海 (grid1[r][c]=0)
所以只要對grid2做一次DFS就好了
檢查grid1[r][c]都為1就是sub island
## Complexity
Time, Space: O(MN)
## Code
```python
class Solution:
def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]])
-> int:
len_r, len_c = len(grid1), len(grid1[0])
def dfs(r, c):
res = grid1[r][c]
grid2[r][c] = 0
for dr, dc in (r+1, c), (r-1, c), (r, c+1), (r, c-1):
if 0 <= dr < len_r and 0 <= dc < len_c and grid2[dr][dc]:
res &= dfs(dr, dc)
return res
res = 0
for r in range(len_r):
for c in range(len_c):
if grid2[r][c]:
res += dfs(r, c)
return res
```
--
http://i.imgur.com/OLvBn3b.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 185.213.82.49 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1724831484.A.105.html
討論串 (同標題文章)
完整討論串 (本文為第 776 之 1554 篇)：