My Easy Understanding C++ Solution With BFS


  • 0
    B
    
    class Solution {
    private:
        struct Coodinate2D{
            int x;
            int y;
            Coodinate2D(int a,int b):x(a),y(b){}
        };
    public:
        int islandPerimeter(std::vector<std::vector<int>>& grid) {
            if (grid.size()==0)
                return 0;
            bool bVisited[grid.size()][grid[0].size()];
            int result=0;
            memset(bVisited,0,grid.size()*grid[0].size());
            std::deque<Coodinate2D> deque;
            for(int x=0;x<grid.size();x++)
                for(int y=0;y<grid[0].size();y++)
                    if (grid[x][y]==1){
                        deque.push_back(Coodinate2D(x,y));
                        break;
                    }
            while(deque.size()!=0){
                const Coodinate2D &  coodinate2D = deque.front();
                if (coodinate2D.x<0 || coodinate2D.x>=grid.size() ||
                        coodinate2D.y<0||coodinate2D.y>=grid[0].size()||!grid[coodinate2D.x][coodinate2D.y]){
                    result++;
                }else if(!bVisited[coodinate2D.x][coodinate2D.y]) {
                        deque.push_back(Coodinate2D(coodinate2D.x - 1, coodinate2D.y));
                        deque.push_back(Coodinate2D(coodinate2D.x + 1, coodinate2D.y));
                        deque.push_back(Coodinate2D(coodinate2D.x, coodinate2D.y - 1));
                        deque.push_back(Coodinate2D(coodinate2D.x, coodinate2D.y + 1));
                        bVisited[coodinate2D.x][coodinate2D.y]=true;
                }
                deque.pop_front();
            }
            return result;
        }
    };

Log in to reply
 

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