Number of island
Medium; BFS;
1. Link
2. 描述
给一个01矩阵,1代表是陆地,0代表海洋, 如果两个1相邻,那么这两个1属于同一个岛。我们只考虑上下左右为相邻。 岛屿: 相邻陆地可以组成一个岛屿(相邻:上下左右) 判断岛屿个数。
示例1
输入:
[[1,1,0,0,0],[0,1,0,1,1],[0,0,0,1,1],[0,0,0,0,0],[0,0,1,1,1]]
复制返回值:
3
复制
备注:
01矩阵范围<=200*200
3. 描述
BFS
iterate every element in array
at current element, use BFS to search all adjacent element with value =1 and mark them as -1, visited, and count the area of this island
then island count += 1 if the area of current node >0
Time: O(n), Space: O(# of node in this level)
4. Coding
class Solution:
def solve(self , grid ):
# write code here
# 1. input: 2D char array, output: number of island
# 2. BFS
# iterate every node in matrix,
# start from current node do BFS using a queue
# when queue is not empty
# if node is 1 then mark the visited node as -1 until all reachable
# node is found
# then # of island += 1
#
# test case:
#
#
#
if not grid or not grid[0]:
return 0
cnt = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
area = 0
queue = [(i,j)]
while queue:
r,c = queue.pop(0)
if r>=0 and r <len(grid) and c>=0 and c < len(grid[0]) and grid[r][c] == '1':
grid[r][c] = '-1'
queue.extend([(r-1, c), (r, c-1), (r+1, c), (r, c+1)])
area += 1
if area >0:
cnt += 1
return cnt
Last updated
Was this helpful?