- Number of Islands
中等
https://leetcode-cn.com/problems/number-of-islands/
Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return 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:
Input: grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
Output: 1
Example 2:
Input: grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
Output: 3
Constraints:
m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] is '0' or '1'.
相关企业
- 亚马逊 Amazon|102
- 微软 Microsoft|44
- Facebook|34
- 彭博 Bloomberg|33
- 谷歌 Google|25
相关标签
- Depth-First Search
- Breadth-First Search
- Union Find
- Array
- Matrix
相似题目
- Surrounded Regions 中等
- Walls and Gates 中等
- Number of Islands II 困难
- Number of Connected Components in an Undirected Graph 中等
- Number of Distinct Islands 中等
- Max Area of Island 中等
offsets = [[0, 1], [0, -1], [1, 0], [-1, 0]]
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
if not grid or not grid[0]:
return 0
rowlen = len(grid)
collen = len(grid[0])
visitedLand = set() # only 1 will be recorded
islandnum = 0
for i in range(rowlen):
for j in range(collen):
if (i, j) in visitedLand or grid[i][j] == "0":
continue
self.bfsOnLand(grid, i, j, visitedLand)
islandnum += 1
return islandnum
def bfsOnLand(self, grid, x, y, visitedLand):
queue = collections.deque([(x, y)])
visitedLand.add((x, y))
while queue:
currcell = queue.popleft()
curr_x, curr_y = currcell[0], currcell[1]
for offset in offsets:
next_x, next_y = curr_x + offset[0], curr_y + offset[1]
if self.isValid(grid, next_x, next_y, visitedLand):
visitedLand.add((next_x, next_y))
queue.append((next_x, next_y))
def isValid(self, grid, x, y, visitedLand):
rowlen = len(grid)
collen = len(grid[0])
if 0 <= x <= rowlen-1 and 0 <= y <= collen-1:
if (x, y) not in visitedLand:
if grid[x][y] == "1":
return True
return False