Lt463.岛屿的周长、dfs

463. 岛屿的周长

给定一个包含 0 和 1 的二维网格地图，其中 1 表示陆地  0 表示水域。
网格中的格子水平和垂直方向相连（对角线方向不相连）。整个网格被水完全包围，但其中恰好有一个岛屿（或者说，一个或多个表示陆地的格子相连组成的岛屿）。
岛屿中没有“湖”（“湖” 指水域在岛屿内部且不和岛屿周围的水相连）。格子是边长为 1 的正方形。网格为长方形，且宽度和高度均不超过 100 。计算这个岛屿的周长。

 示例 :

输入:
[[0,1,0,0],
 [1,1,1,0],
 [0,1,0,0],
 [1,1,0,0]]
输出: 16
解释: 它的周长是下面图片中的 16 个黄色的边：

思路

双重遍历

对每一个节点，如果为陆地，计数先加上 4，然后判断他上下左右是否为陆地，为陆地则将边减去，如果是最靠外一圈，说明边一定存在，会跳过其靠外的那个边减的过程。根据 i 是否大于 0 小于 grid.length，j 是否大于 0，小于 grid[i].length 来判断。

dfs

只有一个岛屿，所以找到第一个陆地开始深度遍历。
当 x，y 在边界之外时，表示上一个节点的一条边在边界上，边加一。
当 x，y 为 0，表示为水域，边加一。
当 x，y 为 2，表示为陆地且已经遍历过，直接返回 0。
当 x，y 为 1，表示还未遍历过的陆地，对该点的上下左右进行深度遍历。

解答

双重遍历

/**
 * @param {number[][]} grid
 * @return {number}
 */
var islandPerimeter = function (grid) {
  let count = 0;
  for (let i = 0; i < grid.length; i++) {
    for (let j = 0; j < grid[i].length; j++) {
      if (grid[i][j] === 1) {
        count += 4;
        if (i > 0 && grid[i - 1][j] === 1) count--;
        if (j > 0 && grid[i][j - 1] === 1) count--;
        if (j < grid[i].length - 1 && grid[i][j + 1] === 1) count--;
        if (i < grid.length - 1 && grid[i + 1][j] === 1) count--;
      }
    }
  }
  return count;
};

dfs

/**
 * @param {number[][]} grid
 * @return {number}
 */
var islandPerimeter = function (grid) {
  const dfs = (x, y) => {
    if (x < 0 || x > grid.length - 1 || y < 0 || y > grid[0].length - 1)
      return 1;
    if (grid[x][y] === 0) return 1;
    else if (grid[x][y] === 2) return 0;
    else grid[x][y] = 2;
    return dfs(x + 1, y) + dfs(x - 1, y) + dfs(x, y + 1) + dfs(x, y - 1);
  };
  for (let i = 0; i < grid.length; i++) {
    for (let j = 0; j < grid[0].length; j++) {
      if (grid[i][j] === 1) {
        return dfs(i, j);
      }
    }
  }
  return 0;
};