# LC 463. Island Perimeter

### [Problem link](https://leetcode.com/problems/island-perimeter/)

###### tags: `leedcode` `easy` `python` `c++` `BFS`

You are given <code>row x col</code> <code>grid</code> representing a map where <code>grid[i][j] = 1</code> representsland and <code>grid[i][j] = 0</code> represents water.

Grid cells are connected **horizontally/vertically** (not diagonally). The <code>grid</code> 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", meaning the water inside 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 1:**
<img src="https://assets.leetcode.com/uploads/2018/10/12/island.png" style="width: 221px; height: 213px;" />

Input: grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
Output: 16
Explanation: The perimeter is the 16 yellow stripes in the image above.

**Example 2:**

Input: grid = [[1]]
Output: 4

**Example 3:**

Input: grid = [[1,0]]
Output: 4

**Constraints:**

- <code>row == grid.length</code>
- <code>col == grid[i].length</code>
- <code>1 <= row, col <= 100</code>
- <code>grid[i][j]</code> is <code>0</code> or <code>1</code>.
- There is exactly one island in <code>grid</code>.

## Solution 1
#### Python

class Solution:
    def islandPerimeter(self, grid: List[List[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        res = 0

        for i in range(rows):
            for j in range(cols):
                if grid[i][j] == 0:
                    continue
                for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                    new_x, new_y = i + dx, j + dy
                    if new_x in [-1, rows] or new_y in [-1, cols] or grid[new_x][new_y] == 0:
                        res += 1

        return res

#### C++

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

## Solution 2 - DFS
#### C++

class Solution {
public:
    int dfs(vector<vector<int>>& grid, int x, int y) {
        int m = grid.size();
        int n = grid[0].size();
        int dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
        int edgeCnt = 0;
        grid[x][y] = 2;
        for (int i = 0; i < 4; i++) {
            int newX = x + dir[i][0];
            int newY = y + dir[i][1];
            if (0 <= newX && newX < m && 0 <= newY && newY < n) {
                if (grid[newX][newY] == 1) {
                    edgeCnt += dfs(grid, newX, newY);
                } else if (grid[newX][newY] == 0) {
                    edgeCnt++;
                }
            } else {
                edgeCnt++;
            }
        }
        return edgeCnt;
    }

    int islandPerimeter(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    return dfs(grid, i, j);
                }
            }
        }
        return 0;
    }
};

>### Complexity
>| | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1 | O(n) | O(1) |

## Note
sol1 (C++):
假設每個陸地貢獻4個邊, 接下來檢查是否有相鄰的陸地, 每個相鄰的陸地會共用同一個邊, 所以要-2