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.
Example 1:
11110
11010
11000
00000
- Answer: 1
Example 2:
11000
11000
00100
00011
- Answer: 3
C Solution:
void dfs(char **grid, int gridRowSize, int gridColSize, int r, int c) {
grid[r][c] = '0';
if (r > 0 && grid[r - 1][c] == '1') dfs(grid, gridRowSize, gridColSize, r - 1, c);
if (r < gridRowSize - 1 && grid[r + 1][c] == '1') dfs(grid, gridRowSize, gridColSize, r + 1, c);
if (c > 0 && grid[r][c - 1] == '1') dfs(grid, gridRowSize, gridColSize, r, c - 1);
if (c < gridColSize - 1 && grid[r][c + 1] == '1') dfs(grid, gridRowSize, gridColSize, r, c + 1);
}
int numIslands(char** grid, int gridRowSize, int gridColSize) {
int i, j, res = 0;
for (i = 0; i < gridRowSize; i++) {
for (j = 0; j < gridColSize; j++) {
if (grid[i][j] == '1') {
res++;
dfs(grid, gridRowSize, gridColSize, i, j);
}
}
}
return res;
}
Python Solution 1:
class Solution(object):
def numIslands(self, grid):
"""
:type grid: List[List[str]]
:rtype: int
"""
def recu(r, c):
if 0 <= r < len(grid) and 0 <= c < len(grid[0]) and grid[r][c] == '1':
grid[r][c] = '0'
map(recu, (r - 1, r + 1, r, r), (c, c, c - 1, c + 1))
res = 0
for r, row in enumerate(grid):
for c, node in enumerate(row):
if node == '1':
recu(r, c)
res += 1
return res
Python Solution 2:
class Solution(object):
def numIslands(self, grid):
"""
:type grid: List[List[str]]
:rtype: int
"""
if not grid: return 0
id = list(range(len(grid) * len(grid[0])))
self.res = 0
def find(a):
while a != id[a]:
id[a] = a = id[id[a]]
return a
def union(a, b):
aroot = find(a)
broot = find(b)
if aroot == broot: return
id[aroot] = broot
self.res -= 1
for r, row in enumerate(grid):
for c, node in enumerate(row):
if grid[r][c] == '1':
self.res += 1
if r < len(grid) - 1 and grid[r + 1][c] == '1':
union(r * len(grid[0]) + c, (r + 1) * len(grid[0]) + c)
if c < len(grid[0]) - 1 and grid[r][c + 1] == '1':
union(r * len(grid[0]) + c, r * len(grid[0]) + c + 1)
return self.res
Summary:
- Union find?
LeetCode: 200. Number of Islands
近期评论