Number of Islands

Given a 2d grid map of'1's (land) and'0's (water), count 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:

11110
11010
11000
00000

Answer: 1

Example 2:

11000
11000
00100
00011

Answer: 3

这题的目标就是要找到所有都是1的连接块的个数。

我们可以把整个 matrix 都过一遍，遇到一个1我们就把 count+1， 然后我们再从这个坐标使用 bfs 或者 dfs，来把这个1 连接在一起的其他的1都找到，然后把它们全部都变成0来表示我们已经访问过了，然后我们的 循环找到下一个1 在重复这样的工作，我们就能找到所有的连接块了。

DFS

class Solution(object):
    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        # 先判断行是否为0，再判断列是否为0
        if len(grid) == 0 or len(grid[0]) == 0:
            return 0
        row = len(grid)
        col = len(grid[0])
        count = 0

        for i in range(row):
            for j in range(col):
                if grid[i][j] == '1':
                    count += 1
                    self.dfsHelper(grid, i, j)
        return count

    def dfsHelper(self, grid, i, j):
        if grid[i][j] == '0':
            return
        grid[i][j] = '0'
        # up
        if i-1 >= 0:
            self.dfsHelper(grid, i-1, j)
        # down 
        if i+1<=len(grid)-1:
            self.dfsHelper(grid, i+1, j)
        # left
        if j-1>=0:
            self.dfsHelper(grid, i, j-1)
        # right
        if j+1<=len(grid[0])-1:
            self.dfsHelper(grid, i, j+1)

BFS

BFS is to search and store every possible directions(solutions) using a queue usually, then search from the head of the queue each time.

class Solution(object):
    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        # 先判断行是否为0，再判断列是否为0
        if len(grid) == 0 or len(grid[0]) == 0:
            return 0
        row = len(grid)
        col = len(grid[0])
        count = 0

        for i in range(row):
            for j in range(col):
                if grid[i][j] == '1':
                    count += 1
                    self.bfsHelper(grid, i, j)
        return count

    def bfsHelper(self, grid, i, j):
        queue = [(i,j)]
        while queue:
            x,y = queue.pop(0)
            if grid[x][y] == '0':
                continue
            grid[x][y] = '0'
            # up
            if x-1 >= 0:
                queue.append((x-1, y))
            # down 
            if x+1<=len(grid)-1:
                queue.append((x+1,y))
            # left
            if y-1>=0:
                queue.append((x,y-1))
            # right
            if y+1<=len(grid[0])-1:
                queue.append((x,y+1))

Union Find