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).
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;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/24741.html
標籤：其他