0463. Island Perimeter (E)

佚名 4年前 (2020-07-08) 算法 699人围观抢沙发百度已收录

Island Perimeter (E)

题目

You are given a map in form of a two-dimensional integer grid where 1 represents land and 0 represents water.

Grid cells are connected horizontally/vertically (not diagonally). The grid is completely surrounded by water, and there is exactly one island (i.e., one or more connected land cells).

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

The island doesn't have "lakes" (water inside that isn't connected to the water around the island). One cell is a square with side length 1. The grid is rectangular, width and height don't exceed 100. Determine the perimeter of the island.

Example:

Input:
[[0,1,0,0],
 [1,1,1,0],
 [0,1,0,0],
 [1,1,0,0]]

Output: 16

Explanation: The perimeter is the 16 yellow stripes in the image below:

题意

给定一个矩阵图表示的海域，其中有一个连通的小岛，求该小岛的周长。

思路

直接遍历一遍矩阵，对于每一个小岛，判断与它相连的小岛数为n，那么当前小岛贡献的周长就是4-n。

注意到对于小岛这个整体，只要左边有一条边，那么在相同水平位置的右边也有一条边；只要上边有一条边，那么在相同垂直位置的下边也有一条边，所以也可以只统计每个方块左边和上边的贡献，最后乘2即可。

代码实现

Java

统计四边

class Solution {
    public int islandPerimeter(int[][] grid) {
        int perimeter = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) {
                    perimeter += edges(grid, i, j);
                }
            }
        }
        return perimeter;
    }

    private int edges(int[][] grid, int i, int j) {
        int[] diffI = { -1, 0, 1, 0 };
        int[] diffJ = { 0, 1, 0, -1 };
        int count = 4;
        for (int x = 0; x < 4; x++) {
            int nextI = i + diffI[x];
            int nextJ = j + diffJ[x];
            if (nextI >= 0 && nextI < grid.length && nextJ >= 0 && nextJ < grid[0].length && grid[nextI][nextJ] == 1) {
                count--;
            }
        }
        return count;
    }
}

统计两边

class Solution {
    public int islandPerimeter(int[][] grid) {
        int count = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1 && (i == 0 || grid[i - 1][j] == 0)) count++;
                if (grid[i][j] == 1 && (j == 0 || grid[i][j - 1] == 0)) count++;
            }
        }
        return count * 2;
    }
}