A BFS solution


  • 0
    M
    class Solution {
    private:
        struct Point
        {
            int x;
            int y;
            
            Point(int x, int y) : x(x), y(y) {};
        };
        
    public:
        int islandPerimeter(vector<vector<int>>& grid) {
            queue<Point> q;
            vector<vector<int>> visited(grid.size(), vector<int>(grid[0].size(), 0));
            
            int r = 0;
            bool found = false;
            int s = grid[0].size();
            for (int i = 0; i < grid.size(); ++i)
            {
                for (int j = 0; j < s; ++j)
                {
                    if (grid[i][j] == 1)
                    {
                        found = false;
                        
                        q.push(Point(i, j));
                        break;
                    }
                }
                
                if (found)
                {
                    break;
                }
            }
            
            while (!q.empty())
            {
                Point c = q.front();
                q.pop();
                
                if (visited[c.x][c.y] == 1)
                {
                    continue;
                }
                
                if (c.x == 0)
                {
                    ++r;
                }
                else if (grid[c.x - 1][c.y] == 0)
                {
                    ++r;
                }
                else
                {
                    q.push(Point(c.x - 1, c.y));
                }
                
                if (c.x == grid.size() - 1)
                {
                    ++r;
                }
                else if (grid[c.x + 1][c.y] == 0)
                {
                    ++r;
                }
                else
                {
                    q.push(Point(c.x + 1, c.y));
                }
                
                if (c.y == 0)
                {
                    ++r;
                }
                else if (grid[c.x][c.y - 1] == 0)
                {
                    ++r;
                }
                else
                {
                    q.push(Point(c.x, c.y - 1));
                }
                
                if (c.y == s - 1)
                {
                    ++r;
                }
                else if (grid[c.x][c.y + 1] == 0)
                {
                    ++r;
                }
                else
                {
                    q.push(Point(c.x, c.y + 1));
                }
                
                visited[c.x][c.y] = 1;
            }
            
            return r;
        }
    };
    

Log in to reply
 

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