LintCode Q433 Number of Islands in Python

  • Jinhai ZHOU
  • 4 Minutes
  • 2016年11月1日
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
from collections import deque
class Solution:
# @param {boolean[][]} grid a boolean 2D matrix
# @return {int} an integer
def bfs(self, row, col, row_len, col_len, grid):
queue = deque([[row, col]])
while queue:
[row, col] = queue.popleft()
grid[row][col] = 0
if ((row + 1 < row_len) and grid[row + 1][col]):
queue.append([row + 1, col])
if ((col + 1 < col_len) and grid[row][col + 1]):
queue.append([row, col + 1])
if ((row - 1 >= 0) and grid[row - 1][col]):
queue.append([row - 1, col])
if ((col - 1 >= 0) and grid[row][col - 1]):
queue.append([row, col - 1])
def numIslands(self, grid):
# Write your code here
if not grid:
return 0
island_count = 0
r_len = len(grid)
c_len = len(grid[0])
for row in xrange(len(grid)):
for col in xrange(len(grid[0])):
if grid[row][col]:
island_count += 1
self.bfs(row, col, r_len, c_len, grid)
return island_count
知识共享许可协议
本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。