# [Leetcode #463. Island Perimeter](https://leetcode.com/problems/island-perimeter/)

###### tags:`Matrix` `DFS` `BFS` `Easy`

## Problem
You are given `row x col` `grid` representing a map where `grid[i][j] = 1 `represents land and `grid[i][j] = 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", 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.

### Sample Input and Output
**Example 1**

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 2**

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

<br>

<hr/>

## Solutions

### Most Votes

#### DFS: iterate over grid and measure the perimeter if the cell value is 1

var islandPerimeter = function(grid) {
  if (grid === null) return 0;
  for (let i = 0 ; i < grid.length ; i++){
      for (let j = 0 ; j < grid[0].length ; j++){
          if (grid[i][j] === 1) {
              return getPerimeter(grid,i,j);
          }
      }
  }
  return 0;  
};

function getPerimeter(grid, i, j){
    if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length) {
        return 1;
    }

    if (grid[i][j] === 0) {
        return 1;
    }

    if (grid[i][j] === -1) return 0;

    let count = 0;
    grid[i][j] = -1;

    count += getPerimeter(grid, i-1, j);
    count += getPerimeter(grid, i, j-1);
    count += getPerimeter(grid, i, j+1);
    count += getPerimeter(grid, i+1, j);

    return count;

}

#### BFS: for each land cell add up the perimeter

var islandPerimeter = function(grid) {
    const rows = grid.length;
    const cols = grid[0].length;
    
    let perimeter = 0;
    
    for (let row = 0; row < rows; row++) {
        for (let col = 0; col < cols; col++) {
            if (!grid[row][col]) continue;
            
            perimeter += 4;
            
            if (row > 0 && grid[row - 1][col]) perimeter -= 2;
            if (col > 0 && grid[row][col - 1]) perimeter -= 2;
        }
    }
    
    return perimeter;
};

### Complexity analysis

**Time complexity : `O(mn)`**
where `m` is the length of the row, `n` is the length of the column

**Space complexity (extra) : `O(1)`**

---

### Everyone's

#### DFS

:::spoiler 東

/*
    Time O(m*n) | Space O(m*n) 
    m is the number of row of input grid
    n is the number of colomn of input grid
*/
var islandPerimeter = function(grid) {
   const rowCnt = grid.length;
   const colCnt = grid[0].length;
   let perimeter = 0;
   const visited = new Array(rowCnt).fill().map(() => new Array(colCnt).fill(false));

   function depthFirstTraverse(rowIdx, colIdx){
        if(rowIdx < 0 || rowIdx > rowCnt - 1 || colIdx < 0 || colIdx > colCnt - 1 || grid[rowIdx][colIdx] === 0){
            return 1;
            }
        else if(!visited[rowIdx][colIdx]) {
                visited[rowIdx][colIdx] = true;
                let currPerim = 0;
                currPerim += depthFirstTraverse(rowIdx + 1, colIdx);
                currPerim += depthFirstTraverse(rowIdx, colIdx + 1);
                currPerim += depthFirstTraverse(rowIdx - 1, colIdx);
                currPerim += depthFirstTraverse(rowIdx, colIdx - 1);
                perimeter += currPerim;
            }
        return 0;
    }

   for(let i = 0; i < rowCnt; i++){
       for(let j = 0; j < colCnt; j++){
           if(grid[i][j] === 1){
               depthFirstTraverse(i, j);
               return perimeter;
           }
       }
   }
};

:::

#### BFS
:::spoiler 月

/* Time: O(n*m) | Space: O(1)
   n, m is the length and width of the island.
*/
var islandPerimeter = function(grid) {
  let perimeter = 0;
  for (let i = 0; i < grid.length; i++) {
    for (let j = 0; j < grid[0].length; j++) {
      if (grid[i][j]) {
        perimeter += 4;
        if (grid[i - 1] && grid[i - 1][j]) perimeter--;
        if (grid[i + 1] && grid[i + 1][j]) perimeter--;
        if (grid[i] && grid[i][j - 1]) perimeter--;
        if (grid[i] && grid[i][j + 1]) perimeter--;
      }
    }
  }
  return perimeter;
}

:::

<br>

:::spoiler YC

let subtracted = 0;
let land = 0;

var islandPerimeter = function(grid) {

    const x = grid.length;
    const y = grid[0].length;
    
    for(let i = 0; i < x; i++){
        for(let j = 0; j < y; j++){
            if(grid[i][j] !== 1) continue;
            
            land++;
            
            checkAdjacent(i-1, j, grid);
            checkAdjacent(i+1, j, grid);
            checkAdjacent(i, j-1, grid);
            checkAdjacent(i, j+1, grid);
        }
    }
    
    return land * 4 - subtracted;
};

function checkAdjacent(i, j, grid){
    if(i < 0 || j < 0 || i >= grid.length || j >= grid[0].length) return;
    if(grid[i][j] === 0) return;
    
    subtracted++;
}

:::

<br>

#### backlog

:::spoiler Hao

:::

<br>

---

## Supplement / Discussion