c++ solution


  • 0
    M
    class Solution {
    private:
        bool isValid(vector<vector<int>>& grid, int row, int col){
            return row >= 0 && col >= 0 && row < grid.size() && col < grid[0].size();
        }
        
        vector<pair<int, int>> getNeighbours(int row, int col){
            vector<pair<int, int>> neighbours;
            vector<pair<int, int>> directions = {make_pair(0,1), make_pair(0,-1), make_pair(1,0), make_pair(-1,0)};
            
            for(auto direction: directions){
                neighbours.push_back(make_pair(row + direction.first, col + direction.second));
            }
            return neighbours;
        }
        
        int computePerimeter(vector<vector<int>> &grid, int row, int col){
            int perimeter = 0;
            queue<pair<int, int>> bfsQueue;
            
            bfsQueue.push(make_pair(row, col));
            
            while(!bfsQueue.empty()){
                pair<int, int> temp = bfsQueue.front();
                bfsQueue.pop();
                int count = 0;
    
                grid[temp.first][temp.second] = 2;
                
                for(auto neighbour: getNeighbours(temp.first, temp.second)){
                    if(isValid(grid, neighbour.first, neighbour.second) && grid[neighbour.first][neighbour.second] != 0){
                        count++;
                    }
                    if(isValid(grid, neighbour.first, neighbour.second) && grid[neighbour.first][neighbour.second] == 1){
                        grid[neighbour.first][neighbour.second] = 2;
                        bfsQueue.push(make_pair(neighbour.first, neighbour.second)); 
                        
                    }   
                }
                perimeter += (4-count);
            }
            return perimeter;
        }
        
    public:
        int islandPerimeter(vector<vector<int>>& grid) {
            int perimeter;
            for(int i = 0; i<grid.size(); i++){
                for(int j = 0 ; j<grid[0].size(); j++){
                    if(grid[i][j] == 1){
                        perimeter = computePerimeter(grid, i,j);
                        break;
                    }
                }
            }
            return perimeter;
        }
    };
    

Log in to reply
 

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