leetcode Questions: Number of Islands

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

Analysis:

This is a typical recursive problem which can be solved by either Depth First Search(DFS) or Breath First Search (BFS).

Briefly speaking, DFS is to search every possible directions(solutions) whenever meet the new one, BFS is to search and store every possible directions(solutions) using a queue usually, then search from the head of the queue each time.

In this problem, possible directions are left, right, top, bottom, with constrains that the new location is '1' and has not been visited before. Therefore, we can define a bool matrix (of same size) to store the status of each element in the grid, set it to false when it is not available(been visited).

Details can be found in the code below, which is pretty straightforward.

Code(C++, DFS):

class Solution {
public:

    void search(int i, int j, vector<vector<char>>& grid, vector<vector<bool>>& mark){
        mark[i][j] = false;
        
        if (i+1<grid.size() && grid[i+1][j]=='1' && mark[i+1][j]==true){
            search(i+1,j,grid,mark);
        }
        if (j+1<grid[0].size() && grid[i][j+1]=='1' && mark[i][j+1]==true){
            search(i,j+1,grid,mark);
        }
        if (i-1>=0 && grid[i-1][j]=='1' && mark[i-1][j]==true){
            search(i-1,j,grid,mark);
        }
        if (j-1>=0 && grid[i][j-1]=='1' && mark[i][j-1]==true){
            search(i,j-1,grid,mark);
        }
    }    

    int numIslands(vector<vector<char>>& grid) {
        int row = grid.size();
        if (row==0) return 0;
        int col = grid[0].size();
        
        int res=0;
        
        vector<vector<bool> > mark(row, vector<bool>(col,true));
        
        for (int i=0;i<row;i++){
            for (int j=0;j<col;j++){
                if (grid[i][j] == '1' && mark[i][j] == true){
                    search(i,j,grid,mark);
                    res+=1;
                }
            }
        }
        return res;
        
    }
};

Code(C++, BFS):

class Solution {
public:

    int numIslands(vector<vector<char>>& grid) {
        int row = grid.size();
        if (row==0) return 0;
        int col = grid[0].size();
        
        int res=0;
        
        vector<vector<bool> > mark(row, vector<bool>(col,true));
        
        queue<int> q_row;
        queue<int> q_col;
        
        for (int i=0; i<row; i++){
            for (int j=0; j<col; j++){
                if (grid[i][j]=='1' && mark[i][j]){
                    q_row.push(i);
                    q_col.push(j);
                    mark[i][j] = false;
                    while (!q_row.empty()){
                        int ii = q_row.front();
                        int jj = q_col.front();
                        
                        if (ii+1<row && grid[ii+1][jj]=='1' && mark[ii+1][jj]){
                            q_row.push(ii+1);
                            q_col.push(jj);
                            mark[ii+1][jj] = false;
                        }
                        if (jj+1<col && grid[ii][jj+1]=='1' && mark[ii][jj+1]){
                            q_row.push(ii);
                            q_col.push(jj+1);
                            mark[ii][jj+1] = false;
                        }
                        if (ii-1 >=0 && grid[ii-1][jj]=='1' && mark[ii-1][jj]){
                            q_row.push(ii-1);
                            q_col.push(jj);
                            mark[ii-1][jj] = false;
                        }
                        if (jj-1>=0 && grid[ii][jj-1]=='1' && mark[ii][jj-1]){
                            q_row.push(ii);
                            q_col.push(jj-1);
                            mark[ii][jj-1] = false;
                        }
                        
                        q_row.pop();
                        q_col.pop();
                    }
                    res += 1;
                }
            }
        }
        return res;
    }
};

Code(Python, DFS):

class Solution:
    
    def search(self, i, j, grid, mark):
        mark[i][j] = False
        
        if i+1 < len(grid) and grid[i+1][j] == '1' and mark[i+1][j] == True:
            self.search(i+1,j,grid,mark)
            
        if j+1 < len(grid[0]) and grid[i][j+1] == '1' and mark[i][j+1] == True:
            self.search(i,j+1,grid,mark)
            
        if i-1 >= 0 and grid[i-1][j] == '1' and mark[i-1][j] == True:
            self.search(i-1,j,grid,mark)
            
        if j-1 >=0 and grid[i][j-1] == '1' and mark[i][j-1] == True:
            self.search(i,j-1,grid,mark)
    
    # @param {character[][]} grid
    # @return {integer}
    def numIslands(self, grid):
        row = len(grid)
        if row == 0:
            return 0
        col = len(grid[0])
        
        #mark = [x[:] for x in [[True]*col]*row]
        mark = [[True for x in range(col)] for x in range(row)]
        
        res  = 0
        for i in range(0,row):
            for j in range(0, col):
                if grid[i][j] == '1' and mark[i][j] == True:
                    self.search(i, j, grid,mark)
                    res += 1
        return res
        

Code(Python, BFS):

class Solution:
    # @param {character[][]} grid
    # @return {integer}
    def numIslands(self, grid):
        row = len(grid)
        if row == 0:
            return 0
        col = len(grid[0])
        
        #mark = [x[:] for x in [[True]*col]*row]
        mark = [[True for x in range(col)] for x in range(row)]
        
        res  = 0
        
        q = []
        
        for i in range(0,row):
            for j in range(0, col):
                if grid[i][j] == '1' and mark[i][j] == True:
                    q.append([i,j])
                    mark[i][j] = False
                    while q:
                        ii = q[0][0]
                        jj = q[0][1]
                        q.pop(0)
                        
                        if ii+1 < len(grid) and grid[ii+1][jj] == '1' and mark[ii+1][jj] == True:
                            q.append([ii+1, jj])
                            mark[ii+1][jj] = False
                
                        if jj+1 < len(grid[0]) and grid[ii][jj+1] == '1' and mark[ii][jj+1] == True:
                            q.append([ii, jj+1])
                            mark[ii][jj+1] = False
                
                        if ii-1 >= 0 and grid[ii-1][jj] == '1' and mark[ii-1][jj] == True:
                            q.append([ii-1, jj])
                            mark[ii-1][jj] = False
                
                        if jj-1 >=0 and grid[ii][jj-1] == '1' and mark[ii][jj-1] == True:
                            q.append([ii, jj-1])
                            mark[ii][jj-1] = False
                    res += 1        
                        
        return res