关关的刷题日记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;
    }
};

人生易老，唯有陪伴最长情，加油！

以上就是关关关于这道题的总结经验，希望大家能够理解，有什么问题可以在我们的专知公众号平台上交流或者加我们的QQ专知-人工智能交流群 426491390，也可以加入专知——Leetcode刷题交流群（请先加微信小助手weixinhao: Rancho_Fang）。 同时请，关注我们的公众号，获取最新关于专知以及人工智能的资讯、技术、算法等内容。扫一扫下方关注我们的微信公众号。