[LeetCode]Island Perimeter

这道题可以用DFS解，找所有能够通过的边从而到达0或者界外。但是这道题还有另外一种非常直观的解法，对于每一个单位square，我们首先默认总的perimeter加4，如果其上面有相邻的sqaure，那么需要减去两个square重叠的两条边，所以需要减2，左边如果有相邻的同理。为何避免重复计算，我们只检查上面和左边，不查右边和下边。时间复杂度O(m * n)，假设输入m行n列，代码如下：

	class Solution {
	public:
	int islandPerimeter(vector<vector<int>>& grid) {
	int m = grid.size(), n = m? grid[0].size(): 0, res = 0;
	if(!m || !n)return 0;
	for(int i = 0; i < m; ++i)
	{
	for(int j = 0; j < n; ++j)
	{
	if(grid[i][j])
	{
	res += 4;
	if(i > 0 && grid[i - 1][j])res -= 2;
	if(j > 0 && grid[i][j - 1])res -= 2;
	}
	}
	}
	return res;
	}
	};

view raw Island Perimeter.cpp hosted with ❤ by GitHub