DFS C++ 9ms


  • 0
    J

    If we encounter an unvisited grid, then increase the island number (count++), mark the grid as visited. Then start from the grid, mark all connected '1' grids as visited (use DFS).
    Finally, return 'count'.

    Similar to connected component problem.

    class Solution {
    public:
        int numIslands(vector<vector<char>>& grid) {
            int count = 0;
            queue<pair<int,int>> myqueue;
            for (int i = 0; i < grid.size(); i++) {
                for (int j = 0; j < grid[i].size(); j++) {
                    if (grid[i][j] == '1') {
                        count++;
                        myqueue.push(make_pair(i,j));
                        grid[i][j] = 'a';
                    }
                    while (!myqueue.empty()) {
                        pair<int,int> mypair = myqueue.front();
                        int m = mypair.first;
                        int n = mypair.second;
                        myqueue.pop();
                        if (m-1 >= 0) { 
                            if (grid[m-1][n] == '1') { grid[m-1][n] = 'a'; myqueue.push(make_pair(m-1,n)); }
                        }
                        if (m+1 < grid.size()) {
                            if (grid[m+1][n] == '1') { grid[m+1][n] = 'a'; myqueue.push(make_pair(m+1,n)); }
                        }
                        if (n-1 >= 0) {
                              if (grid[m][n-1] == '1') { grid[m][n-1] = 'a'; myqueue.push(make_pair(m,n-1)); }
                        }
                        if (n+1 < grid[0].size()) {
                            if (grid[m][n+1] == '1') { grid[m][n+1] = 'a'; myqueue.push(make_pair(m,n+1)); }
                        }                  
                    }
                }
            }
            return count;
        }
    };
    

Log in to reply
 

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