Number of islands#
Practice Link#
LeetCode
Description#
- Given a 2d grid map of ‘1’s (land) and ‘0’s (water), count the number of islands.
- An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically.
- You may assume all four edges of the grid are all surrounded by water.
Examples#
1Input:
211110
311010
411000
500000
6Output: 1
1Input:
211000
311000
400100
500011
6Output: 3
Python Solution#
1class Solution(object):
2 # Iterate through each of the cell and if it is an island,
3 # do dfs to mark all adjacent islands,
4 # then increase the counter by 1.
5 def numIslands(self, grid):
6 if not grid:
7 return 0
8
9 count = 0
10 for i in range(len(grid)):
11 for j in range(len(grid[0])):
12 if grid[i][j] == '1':
13 self.dfs(grid, i, j)
14 count += 1
15 return count
16
17 def dfs(self, grid, i, j):
18 if i < 0 or j < 0 or i >= len(grid) or j >= len(
19 grid[0]) or grid[i][j] != '1':
20 return
21 grid[i][j] = '#'
22 self.dfs(grid, i + 1, j)
23 self.dfs(grid, i - 1, j)
24 self.dfs(grid, i, j + 1)
25 self.dfs(grid, i, j - 1)