C++ 115ms 99% simply go through the table without DFS


  • 0
    7

    Idea: We can, instead of looking at the grid of "points", look at the grid of "edges". Except the case at the limit x=0, x=grid.size()-1, y=0, y=grid.size(), we can tell whether an edge is in our perimeter by calculating xor of its left (up resp.) point and right (down resp.) point.

    class Solution {
    public:
        int islandPerimeter(vector<vector<int>>& grid) {
            int m=grid.size();if(m==0)return 0;
            int n=grid[0].size();
            int result=0;
            for(int i=0;i<m;i++)result+=grid[i][0]+grid[i][n-1];
            for(int j=0;j<n;j++)result+=grid[0][j]+grid[m-1][j];
            for(int i=1;i<m;i++){
                for(int j=0;j<n;j++){
                    result+=grid[i-1][j]^grid[i][j];
                }
            }
            for(int i=0;i<m;i++){
                for(int j=1;j<n;j++){
                    result+=grid[i][j-1]^grid[i][j];
                }
            }
            return result;
        }
    };
    

Log in to reply
 

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