Problem
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:
Solution: Counting
If a land has 0 neighbour, it contributes 4 to the perimeter
If a land has 1 neighbour, it contributes 3 to the perimeter
If a land has 2 neighbours, it contributes 2 to the perimeter
If a land has 3 neighbours, it contributes 1 to the perimeter
If a land has 4 neighbours, it contributes 0 to the perimeter
perimeter = area * 4 – total_neighbours
Time complexity: O(mn)
Space complexity: O(1)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
// Author: Huahua // Running time: 148 ms class Solution { public: int islandPerimeter(vector<vector<int>>& grid) { if (grid.empty()) return 0; int m = grid.size(); int n = grid[0].size(); int area = 0; int conn = 0; for (int y = 0; y < m; ++y) for (int x = 0; x < n; ++x) if (grid[y][x] == 1) { ++area; if (y > 0 && grid[y - 1][x] == 1) ++conn; if (x > 0 && grid[y][x - 1] == 1) ++conn; } return area*4 - conn*2; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment