LintCode Q433 Number of Island dfs 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
from collections import deque
class Solution:
# @param {boolean[][]} grid a boolean 2D matrix
# @return {int} an integer
def dfs(self, row, col, row_len, col_len, grid):
if row >= row_len or row < 0 or col >= col_len or col < 0:
return
if grid[row][col]:
grid[row][col] = 0
self.dfs(row - 1, col, row_len, col_len, grid)
self.dfs(row + 1, col, row_len, col_len, grid)
self.dfs(row, col - 1, row_len, col_len, grid)
self.dfs(row, col + 1, row_len, col_len, grid)
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.dfs(row, col, r_len, c_len, grid)
return island_count
知识共享许可协议
本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。