Leetcode 463. Island Perimeter 解题
Leetcode 463. Island Perimeter 解题
好久没有刷题，甚是怀念这种刷题的感觉 最近有刷杭电oJ POJ也试着刷了一下，还有个国外的平台我忘了叫啥了 感觉LeetCode的平台很人性化，能够在提交之前自己尝试运行，并且能够告诉你WA之前最后一次测试数据是什么，方便寻找错误原因，并且AC之后还能看到别人的AC代码（这是我最欣赏的一点！）这样就能学习到更好的算法，不过它的playground我还不是很会用，调试还得在本地进行。但是测试用例有点少，题目偏简单，相比之下杭电OJ和POJ的测试条件就有点苛刻了
看下题目
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表示，1表示陆地，0表示海洋，整个数组都是被海洋包围，意味着边界之外就是海洋，这个陆地是没有湖的（也就是陆地中间一圈是水）你要找到这个陆地的边界周长
Example:
[[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:
解题思路
遍历整个数组，对每一个是陆地的格子，判断它的四周是否是陆地边缘 陆地边缘的判定标准是：1）是海洋和陆地的分界线 2）是整个数组的边缘 满足这两个条件之一的就是一条边界，一个格子最多有4条边界，把边界累加就可以了。 下面是代码：
class Solution {
public:
int islandPerimeter(vector<vector<int>>& grid) {
int edgs=0;
int height=grid.size();
int width=grid[0].size();
//traverse each cell of the array,check its neighbor
for(int i =0;ifor(int j=0;j//if there is a island
if(grid[i][j]==1){
//up
if((i-1)<0||grid[i-1][j]==0){
edgs++;
}
//down
if((i+1)>=height||grid[i+1][j]==0){
edgs++;
}
//left
if((j-1)<0||grid[i][j-1]==0){
edgs++;
}
//right
if((j+1)>=width||grid[i][j+1]==0){
edgs++;
}
}
}
}
return edgs;
}
};更好的算法
我在浏览其他AC代码的时候看到一个，这个思路很有趣 同样是遍历整个数组，然后每遇到一个陆地，就累计陆地的数目，并且判断陆地内的区域的右边和下面是否同样是陆地，如果是就表明这个不是边界，将这样的数量累加，最后用陆地数量*4-非边界数量即可 只判断右边和下面的目的是为了避免重复计算 下面是代码：
class Solution {
public:
int islandPerimeter(vector<vector<int>>& grid) {
if (grid.empty()) return 0;
int m = grid.size();
int n = grid[0].size();
int islands = 0, neighbours = 0;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (grid[i][j] == 1) {
islands++;
if (i < m - 1 && grid[i + 1][j] == 1) neighbours++;
if (j < n - 1 && grid[i][j + 1] == 1) neighbours++;
}
return islands * 4 - neighbours * 2;
}
};腾讯云开发者
