LEETCODE 200. 岛屿数量

LEETCODE 200. 岛屿数量

题目描述

给定一个由 ‘1’(陆地)和 ‘0’(水)组成的的二维网格,计算岛屿的数量。一个岛被水包围,并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。

示例 1:
输入:
11110
11010
11000
00000
输出: 1

示例 2:
输入:
11000
11000
00100
00011
输出: 3

题目地址

中文版

英文版

 

代码实现

class Solution(object):
	def numIslands(self, grid):
		"""
		:type grid: List[List[str]]
		:rtype: int
		"""
		if(not grid or len(grid[0])==0):
			return 0
		n = len(grid)
		m = len(grid[0])
		def recursion(i,j):
			if(0<=i<n and 0<=j<m and grid[i][j]=="1"):
				grid[i][j] = "0"
				recursion(i-1,j)
				recursion(i+1,j)
				recursion(i,j+1)
				recursion(i,j-1)
		total = 0
		for i in xrange(n):
			for j in xrange(m):
				if(grid[i][j]=="1"):
					recursion(i,j)
					total += 1
		return total
                                                                        
2 次阅读

发表评论

电子邮件地址不会被公开。