Number of Islands

Question

Given a boolean 2D matrix, find the number of islands.

Example

Given graph:

[
  [1, 1, 0, 0, 0],
  [0, 1, 0, 0, 1],
  [0, 0, 0, 1, 1],
  [0, 0, 0, 0, 0],
  [0, 0, 0, 0, 1]
]

return 3.

Analysis

几个方向算联通？

Thoughts

BFS 用一个2d matrix保存访问过的信息

loop throught all the elements, 每当发现一个1时，加一个island,并且遍历它的所有邻居，设为visited

Solution

class Solution:
    # @param {boolean[][]} grid a boolean 2D matrix
    # @return {int} an integer
    def numIslands(self, grid):
        # Write your code here
        if not grid:
            return 0
        rowNum = len(grid)
        colNum = len(grid[0])
        self.visited = [[ False for i in range(colNum)] for j in range(rowNum)]
        numIslands = 0
        for i in range(rowNum):
            for j in range(colNum):
                if self.visited[i][j]:
                    continue
                else:                                                          
                    if grid[i][j]:
                        numIslands += 1           
                        self.dfs(grid, i, j)
                    else:                         
                        self.visited[i][j] = True
        return numIslands

    def dfs(self, grid, i, j):   
        self.visited[i][j] = True
        neighbors = []                             
        if i != 0:                                 
            leftNeighbor = grid[i-1][j]            
            if leftNeighbor and not self.visited[i-1][j]:
                neighbors.append([i-1,j])          
            else:                                  
                self.visited[i-1][j] = True        
        if j != 0:                                 
            upNeighbor = grid[i][j-1]              
            if upNeighbor and not self.visited[i][j-1]:
                neighbors.append([i,j-1])          
            else:                                  
                self.visited[i][j-1] = True        
        if i != len(grid) - 1:                  
            rightNeighbor = grid[i+1][j]           
            if rightNeighbor and not self.visited[i+1][j]:
                neighbors.append([i+1,j])          
            else:                                  
                self.visited[i+1][j] = True        
        if j != len(grid[0]) - 1:                     
            downNeighbor = grid[i][j+1]            
            if downNeighbor and not self.visited[i][j+1]:
                neighbors.append([i,j+1])          
            else:                                  
                self.visited[i][j+1] = True        
        for neighbor in neighbors:                 
            self.dfs(grid, neighbor[0], neighbor[1])