8ms c++ solution with explaination


  • 0

    The basic idea is to traverse all the points, every time when current point is land, the program will stop and found out the whole land that is connected with this land, and mark them as traversed (by giving them value -1).

    So the sub problem now is to solve the problem of finding connected land. This we can use DFS and traversed mark. Every time we find a land, we use DFS on its nearby & not traversed land.

    The c++ solution is as follows:

    public:
        int numIslands(vector<vector<char>>& grid) {
            int result=0;
            for (int i=0;i<grid.size();i++){
                for (int j=0;j<grid[0].size();j++){
                    if (grid[i][j]=='1'){
                        result += 1;
                        dfs(i,j,grid);
                    }
                }
            }
            return result;
        }
        
        void dfs(int i,int j,vector<vector<char>>& grid){
            grid[i][j] = -1;
            if (i+1<grid.size() && grid[i+1][j]=='1') dfs(i+1,j,grid);
            if (j+1<grid[0].size() && grid[i][j+1]=='1') dfs(i,j+1,grid);
            if (i-1<grid[0].size() && grid[i-1][j]=='1') dfs(i-1,j,grid);
            if (j-1<grid[0].size() && grid[i][j-1]=='1') dfs(i,j-1,grid);
        }
        
    };

Log in to reply
 

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