463 Island Perimeter

题目

463 Island Perimeter

题解

小岛的周长就是它的外边缘的长度，而外边缘就是邻接大海而不是邻接小岛的边。

通过观察可以发现，对于某个小岛方格\((row,col)\)上的四条边，当且仅当它们不与其他小岛方格上的边重叠时，这些边才是小岛外边缘的一部分。例如，若邻接的方格\((row+1,col)\)上存在小岛，那么小岛方格\((row,col)\)的下边缘一定不是小岛的外边缘，因为在它的下边还有一个小岛方格。这个规律对于其他方向也同样成立。

找到这个规律之后，求解就相当简单了。只要对每个小岛方格\((i,j)\)检测它上下左右是否有邻接小岛，并统计出不重叠的边的总数就行了。

代码

class Solution {
public:
	int islandPerimeter(vector<vector<int>>& grid) {
		int result = 0;

		int row = grid.size();
		for (int i = 0; i < row; i++)
		{
			int column = grid[i].size();
			for (int j = 0; j < column; j++)
			{
				if (grid[i][j] == 1) {
					if (i == 0 || grid[i - 1][j] == 0)
						result++;
					if (i == row - 1 || grid[i + 1][j] == 0)
						result++;
					if (j == 0 || grid[i][j - 1] == 0)
						result++;
					if (j == column - 1 || grid[i][j + 1] == 0)
						result++;
				}
			}
		}

		return result;
	}
};