200 Numbers of Islands

思路方法很多。

方法一：DFS， 深度优先搜索，可以使用栈或者使用回溯的方法实现。

方法二：BFS， 广度优先搜索，可以使用队列实现。

方法三：并查集，使用并查集将集合做合并

class Solution(object):
    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        if grid is None or len(grid) == 0 or len(grid[0]) == 0:
            return 0

        row, column, ans = len(grid), len(grid[0]), 0 
        vis = [[0 for j in range(column)]for i in range(row)]

        def dfs(x, y, vis):
            dx = [0, 0, -1, 1]
            dy = [1, -1, 0, 0]
            vis[x][y] = 1
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if nx >= row or nx < 0 or ny >= column or ny < 0:
                    continue
                if grid[nx][ny] == '1' and vis[nx][ny] == 0:
                    dfs(nx, ny, vis)

        for i in range(row):
            for j in range(column):
                if grid[i][j] == '1' and vis[i][j] == 0:
                    dfs(i, j, vis)
                    ans += 1
        return ans

class Solution:
    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        if grid ==  []:
            return 0
        nr, nc = len(grid),len(grid[0])
        ans = 0
        for i in range(nr):
            for j in range(nc):
                if(grid[i][j] =='1'):
                    ans += 1
                    queue = []
                    queue.append((i,j))
                    grid[i][j] = '0'
                    while(len(queue)!=0):
                        (cur_x, cur_y) = queue.pop(0)
                        dx = [0,0,1,-1]
                        dy = [1,-1,0,0]
                        for k in range(4):
                            nx = cur_x + dx[k]
                            ny = cur_y + dy[k]
                            if nx < nr and nx >= 0 and ny < nc and ny >=0 and  grid[nx][ny] == '1':
                                queue.append((nx,ny))
                                grid[nx][ny] = '0';
        return ans