leetcode-463-Island Perimeter
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.
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:
要完成的函数：
int islandPerimeter(vector<vector<int>>& grid)
说明：
1、这道题目给定一个二维矩阵，其中1表示是陆地，0表示海洋。要求陆地的周长。
2、我们可以先数出有多少块陆地，记为count，然后数一下每块陆地与多少块接壤，不断加一，记为count1。最后count*4-count1就是我们要的值了。
解释一下为什么这样做就得到结果。因为count*4得到总的边数，每块陆地如果没有接壤的话，每块陆地都要乘以4，才能得到边数。
count1表示有接壤的陆地的总数，比如上面这张图，count1为16，我们也就要减去因为接壤而消失的16条边。
代码如下：
int islandPerimeter(vector<vector<int>>& grid)
{
int count=0,count1=0;//count计算总个数，count1计算每个方块周围有几个
for(int i=0;i<grid.size();i++)
{
for(int j=0;j<grid[i].size();j++)
{
if(grid[i][j]==1)
{
count++;
if(i-1>=0&&grid[i-1][j]==1)//上方
count1++;
if(i+1<grid.size()&&grid[i+1][j]==1)//下方
count1++;
if(j-1>=0&&grid[i][j-1]==1)//左方
count1++;
if(j+1<grid[i].size()&&grid[i][j+1]==1)//右方
count1++;
}
}
}
return count*4-count1;
}上述代码实测227ms，beats 29.09% of cpp submissions。
3、改进：
上述代码还是有点浪费时间，因为进行了四次判断，但其实我们可以只做两次判断，即双重循环内部只做对左方和上方的判断，然后最后这个值乘以2。
代码如下：
int islandPerimeter(vector<vector<int>>& grid)
{
int sizei=grid.size(),sizej=grid[0].size();//行数和列数
int count=0,count1=0;
for(int i=0;i<sizei;i++)
{
for(int j=0;j<sizej;j++)
{
if(grid[i][j]==1)
{
count++;
if(i!=0&&grid[i-1][j]==1)//上方
count1++;
if(j!=0&&grid[i][j-1]==1)//左方
count1++;
}
}
}
return count*4-count1*2;
}上述代码实测189ms，beats 75.10% of cpp submissions。