【LeetCode 463】关关的刷题日记29 Island Perimeter- 专知

【LeetCode 463】关关的刷题日记29 Island Perimeter

点击上方“专知”关注获取更多AI知识!

关关的刷题日记29 – Leetcode 463. Island Perimeter

题目

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.

[[0,1,0,0], [1,1,1,0], [0,1,0,0], [1,1,0,0]]

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

题目的意思是：有一个二维数组里面只有0和1,1表示土地，0表示水。土地被水环绕着，并且里面没有湖，也就是说1是连成一片的，里面没有0，让我们求土地的周长。

思路

思路：我们先用网格数*4算出所有网格的边长和，然后再减去在土地中间的边长。为了避免重复计算，我们只看每个1的左边和上边有没有1与它相连，如果有的话，总体的周长要减去2.

class Solution {public:    int islandPerimeter(vector<vector<int>>& grid) {        int count=0, repeat=0;        for(int i=0; i<grid.size(); i++)        {            for(int j=0; j<grid[i].size(); j++)            {                if(!grid[i][j])                    continue;                count++;                if(i!=0 && grid[i-1][j]==1)                    repeat++;                if(j!=0 && grid[i][j-1]==1)                    repeat++;            }        }        return 4*count-2*repeat;    }};