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.

Solution 1: DFS
Think of a grid as a tree node. While a tree node has only 2 children (left & right), a grid has 4 children (left & right & up & down). Search each of grids ‘s direction by DFS until we cannot find one.

 
public class Solution {
    public int numIslands(char[][] grid) {
        int row = grid.length; 
        if (row == 0) return 0; 
        int col = grid[0].length; 
        int ret = 0; 
        //record whether a grid has been reached 
        boolean marks[][] = new boolean[row][col];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                marks[i][j] = true; 
            }
        }
        
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (grid[i][j] == '1' && marks[i1][j] == true) {
                    search(i, j, grid, marks);
                    ret += 1; 
                }
            }
        }
        return ret; 
    }
    
    public void search (int i, int j, char[][] grid, boolean[][] marks) {
        marks[i][j] = false; //has been reached 
        int row = grid.length; 
        int col = grid[0].length; 
        //Start the DFS 
        if (i-1 >= 0 && grid[i-1][j] == '1' && marks[i-1][j] == true) {
            //left
            search(i-1, j, grid, marks); 
        }
        if (i+1 < row && grid[i+1][j] == '1' && marks[i+1][j] == true) {
            //right 
            search(i+1, j, grid, marks); 
        }
        if (j-1 >= 0 && grid[i][j-1] == '1' && marks[i][j-1] == true) {
            //up
            search(i, j-1, grid, marks);
        }
        if (j+1 < col && grid[i][j+1] == '1' && marks[i][j+1] == true) {
            //down
            search(i, j+1, grid, marks);
        }
    }
}

Solution 2: BFS

 

public class Solution {
    public int numIslands(char[][] grid) {
        int row = grid.length; 
        if (row == 0) return 0; 
        int col = grid[0].length; 
        int ret = 0; 
        //record whether a grid has been reached 
        boolean marks[][] = new boolean[row][col];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                marks[i][j] = true; 
            }
        }
        
        //implement BFS by queue 
        Queue<Integer> q_row = new LinkedList<Integer>();  
        Queue<Integer> q_col = new LinkedList<Integer>(); 
        
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (grid[i][j] == '1' && marks[i][j]) {
                    //insert elements
                    q_row.add(i);
                    q_col.add(j); 
                    marks[i][j] = false; 
                    while (!q_row.isEmpty()) {
                        //access next elements
                        int ii = q_row.peek(); 
                        int jj = q_col.peek(); 
                        
                        if (ii-1 >= 0 && grid[ii-1][jj] == '1' && marks[ii-1][jj]) {
                            q_row.add(ii - 1);
                            q_col.add(jj);
                            marks[ii-1][jj] = false; 
                        }
                        
                        if (ii+1 < row && grid[ii+1][jj] == '1' && marks[ii+1][jj]) {
                            q_row.add(ii + 1);
                            q_col.add(jj);
                            marks[ii+1][jj] = false; 
                        }

                        if (jj+1 < col && grid[ii][jj+1] == '1' && marks[ii][jj+1]) {
                            q_row.add(ii);
                            q_col.add(jj+1);
                            marks[ii][jj+1] = false; 
                        }

                        if (jj-1 >= 0 && grid[ii][jj-1] == '1' && marks[ii][jj-1]) {
                            q_row.add(ii);
                            q_col.add(jj-1);
                            marks[ii][jj-1] = false; 
                        }
                        q_row.remove(); 
                        q_col.remove(); 
                    }
                    ret = ret + 1;
                }
            }
        }
        return ret; 
    }
    
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s