This is same as number of islands except do not count the sharing edges


  • 0
    N

    Perform dfs and add 1 to the perimieter at each terminal condition of dfs. Skip the sharing edges to avoid double counting.

    class Solution {
        public int islandPerimeter(int[][] grid) {
            int n = grid.length;
            if (n == 0) return 0;
            int m = grid[0].length;
            
            int perimeter = 0;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (grid[i][j] == 1) {
                        perimeter += dfs(grid, i, j, n, m);
                        
                    }
                }
            }
            return perimeter;
        }
        
        private int dfs(int[][] grid, int i, int j, int n, int m) {
            int perimeter = 0;
            if (i < 0 || j < 0 || i >= n || j >= m || grid[i][j] == 0) {
                return 1;
            }
            
            if (grid[i][j] == -1) {
                return 0;
            }
            
            grid[i][j] = -1;
            perimeter += dfs(grid, i-1, j, n, m);
            perimeter += dfs(grid, i+1, j, n, m);
            perimeter += dfs(grid, i, j-1, n, m);
            perimeter += dfs(grid, i, j+1, n, m);
            
            return perimeter;
        }
    }
    

Log in to reply
 

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