O(mn) time
count cells and shared edges
res = 4 * cells - 2 * shared edges
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
int islandPerimeter(vector<vector<int>>& grid) {
int cnt = 0, shared = 0;
for(int i = 0; i < grid.size(); ++i) {
for(int j = 0; j < grid[i].size(); ++j) {
if (grid[i][j]) {
++cnt;
shared += (i > 0 && grid[i - 1][j]);
shared += (j > 0 && grid[i][j - 1]);
}
}
}
return 4 * cnt - shared * 2;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class Solution {
public:
int islandPerimeter(vector<vector<int>>& grid) {
int perimeter = 0;
for (int row = 0; row < grid.size(); ++row) {
for (int col = 0; col < grid[row].size(); ++col) {
if (grid[row][col]) {
if (0 == row || 0 == grid[row - 1][col]) {
++perimeter;
}
if (grid.size() == row + 1 || 0 == grid[row + 1][col]) {
++perimeter;
}
if (0 == col || 0 == grid[row][col - 1]) {
++perimeter;
}
if (grid[row].size() == col + 1 || 0 == grid[row][col + 1]) {
++perimeter;
}
}
}
}
return perimeter;
}
};
|