number_of_islands
1# @leet start 2class Solution: 3 def numIslands(self, grid: list[list[str]]) -> int: 4 """ 5 This problem wants us to count the number of islands, where a 1 indicates 6 land, and 0 is water, and an island is either surrounded by water 7 or, if it touches an edge, that is also water. 8 9 To do this, we can iterate through the grid, and when we find an island 10 we continue to check 4-dimensionally around it, marking other 1s we see 11 as part of the same island. 12 Finally, we return that count at the end. 13 """ 14 visited = set() 15 m, n = len(grid), len(grid[0]) 16 count = 0 17 18 def inbounds(y, x): 19 return 0 <= y < m and 0 <= x < n 20 21 def dfs(y, x): 22 if not inbounds(y, x) or (y, x) in visited or grid[y][x] == "0": 23 return 24 visited.add((y, x)) 25 dirs = [(1, 0), (0, 1), (-1, 0), (0, -1)] 26 for dy, dx in dirs: 27 new_y, new_x = dy + y, dx + x 28 dfs(new_y, new_x) 29 30 for y in range(m): 31 for x in range(n): 32 if (y, x) not in visited and grid[y][x] == "1": 33 dfs(y, x) 34 count += 1 35 return count 36 37 38# @leet end 39 40 41def test(): 42 assert 2 + 2 == 4
class
Solution:
3class Solution: 4 def numIslands(self, grid: list[list[str]]) -> int: 5 """ 6 This problem wants us to count the number of islands, where a 1 indicates 7 land, and 0 is water, and an island is either surrounded by water 8 or, if it touches an edge, that is also water. 9 10 To do this, we can iterate through the grid, and when we find an island 11 we continue to check 4-dimensionally around it, marking other 1s we see 12 as part of the same island. 13 Finally, we return that count at the end. 14 """ 15 visited = set() 16 m, n = len(grid), len(grid[0]) 17 count = 0 18 19 def inbounds(y, x): 20 return 0 <= y < m and 0 <= x < n 21 22 def dfs(y, x): 23 if not inbounds(y, x) or (y, x) in visited or grid[y][x] == "0": 24 return 25 visited.add((y, x)) 26 dirs = [(1, 0), (0, 1), (-1, 0), (0, -1)] 27 for dy, dx in dirs: 28 new_y, new_x = dy + y, dx + x 29 dfs(new_y, new_x) 30 31 for y in range(m): 32 for x in range(n): 33 if (y, x) not in visited and grid[y][x] == "1": 34 dfs(y, x) 35 count += 1 36 return count
def
numIslands(self, grid: list[list[str]]) -> int:
4 def numIslands(self, grid: list[list[str]]) -> int: 5 """ 6 This problem wants us to count the number of islands, where a 1 indicates 7 land, and 0 is water, and an island is either surrounded by water 8 or, if it touches an edge, that is also water. 9 10 To do this, we can iterate through the grid, and when we find an island 11 we continue to check 4-dimensionally around it, marking other 1s we see 12 as part of the same island. 13 Finally, we return that count at the end. 14 """ 15 visited = set() 16 m, n = len(grid), len(grid[0]) 17 count = 0 18 19 def inbounds(y, x): 20 return 0 <= y < m and 0 <= x < n 21 22 def dfs(y, x): 23 if not inbounds(y, x) or (y, x) in visited or grid[y][x] == "0": 24 return 25 visited.add((y, x)) 26 dirs = [(1, 0), (0, 1), (-1, 0), (0, -1)] 27 for dy, dx in dirs: 28 new_y, new_x = dy + y, dx + x 29 dfs(new_y, new_x) 30 31 for y in range(m): 32 for x in range(n): 33 if (y, x) not in visited and grid[y][x] == "1": 34 dfs(y, x) 35 count += 1 36 return count
This problem wants us to count the number of islands, where a 1 indicates land, and 0 is water, and an island is either surrounded by water or, if it touches an edge, that is also water.
To do this, we can iterate through the grid, and when we find an island we continue to check 4-dimensionally around it, marking other 1s we see as part of the same island. Finally, we return that count at the end.
def
test():