Solution by DasongLi


  • 2
    D

    Approach #1 Depth First Search [Accepted]

    Intuition

    To traverse the whole islands, we use the Depth First Search to traverse the input matrix. We use one Depth First Search to traverse all the connected points, which combine to be one island. Using this method to traverse other points which have not been visited, We can get the number of the islands and traverse all the islands.

    Algorithm

    • Adding another matrix called vector<vector<int>>& visited to represent the states of all the points. All the initial values are zero.
    • we have a function void dfs(int x, int y, vector<vector<char>>& grid, vector<vector<int>>& visited) . The target of this function is to use depth first search to traverse all the connected points to get one island. After visited one point, this point's state changes to 1.
    • boundary check is if (x<0 || x>=grid.size() || y<0 || y>=grid[0].size())
    • In the function int numIslands(vector<vector<char>>& grid), we invoke the dfs function for the points whose states are 0

    c++

    class Solution {
    public:
        int numIslands(vector<vector<char>>& grid) {
            if (grid.size()==0 or grid[0].size() == 0) return 0;
            int i,j,k,l;
            int width = grid.size(),height = grid[0].size();
            vector<vector<int>> visited;
            for (i=0;i<width;i++) {
                vector<int> tmp;
                for (j=0;j<height;j++) tmp.push_back(0);
                visited.push_back(tmp);
            }
            int res = 0;
            for (i=0;i<width*height;i++) {
                j = i / height; k = i % height;
                if (visited[j][k] == 0 and grid[j][k] == '1') {
                    dfs(j,k,grid,visited);
                    res ++;
                }
            }
            return res;
        }
    private:
        void dfs(int x, int y, vector<vector<char>>& grid, vector<vector<int>>& visited) {
            if (x<0 || x>=grid.size() || y<0 || y>=grid[0].size()) return;
            if (visited[x][y] == 1) return;
            if (grid[x][y] == '0') return;
            visited[x][y] = 1;
            dfs(x+1,y,grid,visited);
            dfs(x-1,y,grid,visited);
            dfs(x,y+1,grid,visited);
            dfs(x,y-1,grid,visited);
        }   
    };
    

    Complexity Analysis

    • Time complexity : O(n^2). The goal of our method is to traverse all the points with value one. Suppose the vector is n*n, the time complexity is O(n^2).
    • Space complexity : O(1). we use & which means reference to achieve the dfs method, constant extra space is used.

    Approach #2 Depth First Search and deleting the state matrix [Accepted]

    Intuition

    The core idea is similar to Approach #1, but it delete vector<vector<int>>& visited and change the vector<vector<char>>& grid to represent the states of points;

    Core Ideas

    • Delete the codes about vector<vector<int>>& visited , which will decrease the space and time to some extend.
    • The values of the vector<vector<char>>& grid are representing the states of points. Zero and one are all the same. But two means the state of the points which has been visited and its original value is one.
    • Other methods is similar to Approach #1.

    c++

    class Solution {
    public:
        int numIslands(vector<vector<char>>& grid) {
            if (grid.size()==0 or grid[0].size() == 0) return 0;
            int i,j,k,l;
            int width = grid.size(),height = grid[0].size();
            /*vector<vector<int> > visited;
            for (i=0;i<width;i++) {
                vector<int> tmp;
                for (j=0;j<height;j++) tmp.push_back(0);
                visited.push_back(tmp);
            }*/
            int res = 0;
            for (i=0;i<width*height;i++) {
                j = i / height; k = i % height;
                if (grid[j][k] == '1') {
                    dfs(j,k,grid);
                    res ++;
                }
            }
            return res;
        }
    private:
        void dfs(int x, int y, vector<vector<char>>& grid) {
            if (x<0 || x>=grid.size() || y<0 || y>=grid[0].size()) return;
            if (grid[x][y] == '0' or grid[x][y] == '2') return;
            grid[x][y] = '2';
            dfs(x+1,y,grid);
            dfs(x-1,y,grid);
            dfs(x,y+1,grid);
            dfs(x,y-1,grid);
        } 
    };
    

    Complexity Analysis

    • Time complexity : O(n^2). The goal of our method is to traverse all the points with value one. Suppose the vector is n*n, the time complexity is O(n^2).
    • Space complexity : O(1). we use & which means reference to achieve the dfs method, constant extra space is used.

    Approach #3 Breadth First Search [Accepted]

    Intuition

    To traverse the whole islands, we use the Breadth First Search to traverse the input matrix. We use one Breadth First Search to traverse all the connected points, which combine to be one island. Using this method to traverse other points which have not been visited, We can get the number of the islands and traverse all the islands.

    Algorithm

    • we have a function bfs(int x,int y,vector<vector<char>>& grid) . The target of this function is to use breadth first search to traverse all the connected points to get one island. After visited one point, this point's state changes to 1.
    • boundary check is if (x<0 || x>=grid.size() || y<0 || y>=grid[0].size())
    • In the function int numIslands(vector<vector<char>>& grid), we invoke the bfs function for the points whose value in grid is one.

    c++

    class Solution {
    public:
        int numIslands(vector<vector<char>>& grid) {
            if (grid.size()==0 or grid[0].size() == 0) return 0;
            int i,j,k,l;
            int width = grid.size(),height = grid[0].size();
            /*vector<vector<int> > visited;
            for (i=0;i<width;i++) {
                vector<int> tmp;
                for (j=0;j<height;j++) tmp.push_back(0);
                visited.push_back(tmp);
            }*/
            int res = 0;
            for (i=0;i<width*height;i++) {
                j = i / height; k = i % height;
                if (grid[j][k] == '1') {
                    dfs(j,k,grid);
                    res ++;
                }
            }
            return res;
        }
    private:
        void bfs(int x,int y,vector<vector<char>>& grid) {
            queue<pair<int,int>> que;
            que.push(pair<int,int>(x,y));
            int xx[4] = {0,0,1,-1},yy[4] = {1,-1,0,0};
            while (!que.empty()) {
                pair<int,int> top = que.front(); que.pop();
                int x = top.first, y = top.second;
                if (x<0 || x>=grid.size() || y<0 || y>=grid[0].size()) continue;
                if (grid[x][y] == '1') {
                    grid[x][y] = '2';
                    que.push(pair<int,int> (x+1,y));
                    que.push(pair<int,int> (x-1,y));
                    que.push(pair<int,int> (x,y-1));
                    que.push(pair<int,int> (x,y+1));
                }
                
            }
        }   
    };
    

    Complexity Analysis

    • Time complexity : O(n^2). The goal of our method is to traverse all the points with value one. Suppose the vector is n*n, the time complexity is O(n^2).
    • Space complexity : O(n^2). We should put all the pairs into the queue, the space complexity is O(n^2).

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.