Concise C++ solution 3ms


  • 0
    K
    class Solution {
    public:
        bool isSafe(vector<vector<char>>&grid, int i, int j, vector<vector<bool>>& processed)
        {   
            return (i >=0) && (i< grid.size()) && (j>=0) && (j<grid[0].size())
                && (grid[i][j]=='1') && (!processed[i][j]);
        }
        void BFS(vector<vector<char>>&grid, int i, int j, vector<vector<bool>>& processed)
        {
            vector<int> row = {-1, 1, 0, 0};
            vector<int> col = {0, 0, -1, 1};
            
            processed[i][j] = true;
            queue<pair<int,int>> q;
            q.push(make_pair(i,j));
            while(!q.empty())
            {
                int x = q.front().first;
                int y = q.front().second;
                q.pop();
                
                for(int i = 0; i < row.size(); i++)
                {
                    if(isSafe(grid, x + row[i], y + col[i], processed))
                    {
                        processed[x + row[i]][y + col[i]] = true;
                        q.push(make_pair(x + row[i], y + col[i]));
                    }
                }
            }
            
        }
        
        int numIslands(vector<vector<char>>& grid) 
        {
            if (grid.empty()) return 0;
            
            vector<vector<bool>> processed(grid.size(), vector<bool>(grid[0].size()));
            
            int count=0;
            
            for(int i = 0 ; i < grid.size(); i++)
            {
                for(int j = 0; j < grid[0].size(); j++)
                {
                    if(!processed[i][j] && grid[i][j]=='1')
                    {
                        BFS(grid, i, j, processed);
                        count++;
                    }
                }
            }
            
            return count;
                
        }
    };
    

    For every place in the matrix with 1, run BFS and the number of calls to BFS indicate the number of islands on the grid.


Log in to reply
 

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