Sponsored
Sponsored
This approach involves iterating over every cell in the grid. For each land cell (grid[i][j] == 1), we assume it initially contributes 4 to the perimeter. We then check its neighboring cells (up, down, left, right). If a neighboring cell is also land, we reduce the perimeter by one for each connection to another land cell, since that edge does not contribute to the perimeter.
Time Complexity: O(n*m) where n is the number of rows and m is the number of columns in the grid.
Space Complexity: O(1) as we only use a constant amount of extra space.
1#include <stdio.h>
2
3int islandPerimeter(int** grid, int gridSize, int* gridColSize) {
4 int perimeter = 0;
5 for (int i = 0; i < gridSize; i++) {
6 for (int j = 0; j < gridColSize[i]; j++) {
7 if (grid[i][j] == 1) {
8 perimeter += 4;
9 if (i > 0 && grid[i-1][j] == 1) perimeter--;
10 if (i < gridSize - 1 && grid[i+1][j] == 1) perimeter--;
11 if (j > 0 && grid[i][j-1] == 1) perimeter--;
12 if (j < gridColSize[i] - 1 && grid[i][j+1] == 1) perimeter--;
13 }
14 }
15 }
16 return perimeter;
17}This C program defines a function that calculates the island perimeter by checking adjacent cells for land. If an adjacent cell is land, the corresponding side does not contribute to the perimeter.
This approach leverages Depth-First Search to traverse the land cells. Starting from any land cell, we recursively visit all connected land cells and calculate the perimeter contribution for each by checking the edges. If an edge points to water or out of bounds, it contributes to the perimeter.
Time Complexity: O(n*m), each cell is visited once.
Space Complexity: O(n*m) for the recursion stack.
1#include <vector>
using namespace std;
class Solution {
public:
int dfs(vector<vector<int>>& grid, int i, int j) {
if (i < 0 || j < 0 || i >= grid.size() || j >= grid[0].size() || grid[i][j] == 0) return 1;
if (grid[i][j] == -1) return 0;
grid[i][j] = -1;
return dfs(grid, i-1, j) + dfs(grid, i+1, j) +
dfs(grid, i, j-1) + dfs(grid, i, j+1);
}
int islandPerimeter(vector<vector<int>>& grid) {
for (int i = 0; i < grid.size(); i++) {
for (int j = 0; j < grid[0].size(); j++) {
if (grid[i][j] == 1) {
return dfs(grid, i, j);
}
}
}
return 0;
}
};This C++ solution implements a Depth-First Search to determine perimeter contributions recursively from the first land cell found.