Leetcode 200.岛屿的个数

Posted on |

200.岛屿的个数

题目

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
示例 1:

输入:
11110
11010
11000
00000

输出: 1
示例 2:

输入:
11000
11000
00100
00011

输出: 3

方法

方法1：深度优先搜索

Iterate through each of the cell and if it is an island, do dfs to mark all adjacent islands, then increase the counter by 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
34
35
36
37
38
class Solution(object):
    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        if not grid:
            return 0

        count=0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j]=='1':
                    self.dfs(grid,i,j)
                    count+=1
        return count

    def dfs(self,grid,i,j):
        if i<0 or j<0 or i>=len(grid) or j>=len(grid[0]) or grid[i][j]!='1':
            return
        grid[i][j]='#'
        # print(i,j,grid)
        self.dfs(grid,i+1,j)
        self.dfs(grid,i-1,j)
        self.dfs(grid,i,j+1)
        self.dfs(grid,i,j-1)

# 输入：[["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]]
# 中间过程：(i,j,grid)
# (0, 0, [['#', u'1', u'1', u'1', u'0'], [u'1', u'1', u'0', u'1', u'0'], [u'1', u'1', u'0', u'0', u'0'], [u'0', u'0', u'0', u'0', u'0']])
# (1, 0, [['#', u'1', u'1', u'1', u'0'], ['#', u'1', u'0', u'1', u'0'], [u'1', u'1', u'0', u'0', u'0'], [u'0', u'0', u'0', u'0', u'0']])
# (2, 0, [['#', u'1', u'1', u'1', u'0'], ['#', u'1', u'0', u'1', u'0'], ['#', u'1', u'0', u'0', u'0'], [u'0', u'0', u'0', u'0', u'0']])
# (2, 1, [['#', u'1', u'1', u'1', u'0'], ['#', u'1', u'0', u'1', u'0'], ['#', '#', u'0', u'0', u'0'], [u'0', u'0', u'0', u'0', u'0']])
# (1, 1, [['#', u'1', u'1', u'1', u'0'], ['#', '#', u'0', u'1', u'0'], ['#', '#', u'0', u'0', u'0'], [u'0', u'0', u'0', u'0', u'0']])
# (0, 1, [['#', '#', u'1', u'1', u'0'], ['#', '#', u'0', u'1', u'0'], ['#', '#', u'0', u'0', u'0'], [u'0', u'0', u'0', u'0', u'0']])
# (0, 2, [['#', '#', '#', u'1', u'0'], ['#', '#', u'0', u'1', u'0'], ['#', '#', u'0', u'0', u'0'], [u'0', u'0', u'0', u'0', u'0']])
# (0, 3, [['#', '#', '#', '#', u'0'], ['#', '#', u'0', u'1', u'0'], ['#', '#', u'0', u'0', u'0'], [u'0', u'0', u'0', u'0', u'0']])
# (1, 3, [['#', '#', '#', '#', u'0'], ['#', '#', u'0', '#', u'0'], ['#', '#', u'0', u'0', u'0'], [u'0', u'0', u'0', u'0', u'0']])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution(object):
    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        if not grid:
            return 0

        self.m,self.n=len(grid),len(grid[0])
        count=0

        for i in range(self.m):
            for j in range(self.n):
                if grid[i][j]=='1':
                    self.dfs(grid,i,j)
                    count+=1
        return count

    def dfs(self,grid,i,j):
        grid[i][j]='0'
        for nr,nc in ((i+1,j),(i-1,j),(i,j+1),(i,j-1)):
            if 0<=nr<self.m and 0<=nc<self.n and grid[nr][nc]=='1':
                    self.dfs(grid,nr,nc)

方法2：广度优先搜索

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
class Solution(object):
    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        if not grid:
            return 0

        self.m,self.n=len(grid),len(grid[0])
        count=0

        for i in range(self.m):
            for j in range(self.n):
                if grid[i][j]=='1':
                    self.bfs(grid,i,j)
                    count+=1
        return count

    def bfs(self,grid,i,j):
        queue=collections.deque([(i,j)])
        grid[i][j]='0'
        while queue:
            r,c=queue.popleft()
            for nr,nc in ((r+1,c),(r-1,c),(r,c+1),(r,c-1)):
                if 0<=nr<self.m and 0<=nc<self.n and grid[nr][nc]=='1':
                    grid[nr][nc]='0'
                    queue.append((nr,nc))
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
34
35
36
class Solution(object):
    def is_valid(self, grid, r, c):
        m, n = len(grid), len(grid[0])
        if r < 0 or c < 0 or r >= m or c >= n:
            return False
        return True

    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        if not grid or not grid[0]:
            return 0

        m, n = len(grid), len(grid[0])
        count = 0
        for i in xrange(m):
            for j in xrange(n):
                if grid[i][j] == '1':
                    self.bfs(grid, i, j)
                    count += 1
        return count

    def bfs(self, grid, r, c):
        queue = collections.deque()
        queue.append((r, c))
        grid[r][c] = '0'
        while queue:
            directions = [(0,1), (0,-1), (-1,0), (1,0)]
            r, c = queue.popleft()
            for d in directions:
                nr, nc = r + d[0], c + d[1]    
                if self.is_valid(grid, nr, nc) and grid[nr][nc] == '1':
                    queue.append((nr, nc))
                    grid[nr][nc] = '0'