岛屿问题篇 ​

const template = grid => {
  const [row, col] = [grid.length, grid[0].length]

  const dfs = (i, j) => {
    // `base case`
    if (i < 0 || i >= row || j < 0 || j >= col) return  // 越界
    if (grid[i][j] !== 'legalValue') return  // 不符合要求
    // 标记（已遍历过）
    grid[i][j] = 'invalidValue'
    dfs(i + 1, j)
    dfs(i - 1, j)
    dfs(i, j - 1)
    dfs(i, j + 1)
  }

  /* 可能会有些预处理 */

  // 遍历
  for (let i = 0; i < row; i++) {
    for (let j = 0; j < col; j++) {
      if (grid[i][j] === 'legalValue') {
        // do something
        dfs(i, j)
      }
    }
  }
}

const numIslands = grid => {
  const [row, col] = [grid.length, grid[0].length]
  let ret = 0

  const dfs = (i, j) => {
    if (i < 0 || i >= row || j < 0 || j >= col) return
    if (grid[i][j] !== '1') return
    grid[i][j] = '2'
    dfs(i + 1, j)
    dfs(i - 1, j)
    dfs(i, j - 1)
    dfs(i, j + 1)
  }

  for (let i = 0; i < row; i++) {
    for (let j = 0; j < col; j++) {
      if (grid[i][j] === '1') {
        ret++
        dfs(i, j)
      }
    }
  }
  return ret
}

const closedIsland = grid => {
  const [row, col] = [grid.length, grid[0].length]
  let ret = 0

  const dfs = (i, j) => {
    if (i < 0 || i >= row || j < 0 || j >= col) return
    if (grid[i][j] !== 0) return
    grid[i][j] = 2
    dfs(i + 1, j)
    dfs(i - 1, j)
    dfs(i, j - 1)
    dfs(i, j + 1)
  }

  // 逻辑上只需要额外先处理边界即可
  for (let i = 0; i < row; i++) {
    // 如果是第一行和最后一行，访问所有格子
    // 如果不是，只访问第一列和最后一列的格子
    const step = (i === 0 || i === row - 1) ? 1 : col - 1
    for (let j = 0; j < col; j += step) {
      dfs(i, j)
    }
  }

  for (let i = 1; i < row; i++) {
    for (let j = 1; j < col; j++) {
      if (grid[i][j] === 0) {
        ret++
        dfs(i, j)
      }
    }
  }
  return ret
}

const countSubIslands = (grid1, grid2) => {
  const [row, col] = [grid1.length, grid1[0].length]
  let ret = 0

  const dfs = (i, j) => {
    if (i < 0 || i >= row || j < 0 || j >= col) return
    if (grid2[i][j] !== 1) return
    grid2[i][j] = 2
    dfs(i + 1, j)
    dfs(i - 1, j)
    dfs(i, j - 1)
    dfs(i, j + 1)
  }

  // 如果在grid1里是水域，在grid2是陆地，把它及邻近的陆地淹掉，排除掉不符合子岛屿的陆地
  for (let i = 0; i < row; i++) {
    for (let j = 0; j < col; j++) {
      if (grid1[i][j] == 0 && grid2[i][j] == 1) {
        dfs(i, j);
      }
    }
  }

  for (let i = 0; i < row; i++) {
    for (let j = 0; j < col; j++) {
      if (grid2[i][j] === 1) {
        ret++
        dfs(i, j)
      }
    }
  }
  return ret
}

const closedIsland = grid => {
  const [row, col] = [grid.length, grid[0].length]
  let ret = 0
  if(row < 3 || col < 3) return ret

  const dfs = (i, j) => {
    if (i < 0 || i >= row || j < 0 || j >= col) return
    if (grid[i][j] !== 1) return
    grid[i][j] = 2
    dfs(i + 1, j)
    dfs(i - 1, j)
    dfs(i, j - 1)
    dfs(i, j + 1)
  }

  // 逻辑上只需要额外先处理边界即可
  for (let i = 0; i < row; i++) {
    // 如果是第一行和最后一行，访问所有格子
    // 如果不是，只访问第一列和最后一列的格子
    const step = (i === 0 || i === row - 1) ? 1 : col - 1
    for (let j = 0; j < col; j += step) {
      dfs(i, j)
    }
  }

  for (let i = 1; i < row; i++) {
    for (let j = 1; j < col; j++) {
      if (grid[i][j] === 1) {
        ret++
      }
    }
  }
  return ret
}

const islandPerimeter = grid => {
  const [row, col] = [grid.length, grid[0].length]

  const dfs = (i, j) => {
    // 边界处提供 一条有效边
    if (i < 0 || i >= row || j < 0 || j >= col) return 1
    // 海洋陆地相交处提供 一条有效边
    if (grid[i][j] === 0) return 1
    if (grid[i][j] !== 1) return 0
    grid[i][j] = 2
    return dfs(i + 1, j)
      + dfs(i - 1, j)
      + dfs(i, j - 1)
      + dfs(i, j + 1)
  }

  for (let i = 0; i < row; i++) {
    for (let j = 0; j < col; j++) {
      if (grid[i][j] === 1) {
        return dfs(i, j)
      }
    }
  }
}

const maxAreaOfIsland = grid => {
  const [row, col] = [grid.length, grid[0].length]
  let ret = 0

  const dfs = (i, j) => {
    if (i < 0 || i >= row || j < 0 || j >= col) return 0
    if (grid[i][j] !== 1) return 0
    grid[i][j] = 2
    return dfs(i + 1, j)
      + dfs(i - 1, j)
      + dfs(i, j - 1)
      + dfs(i, j + 1)
      + 1
  }

  // 求封闭岛屿最大面积
  // for(let i=0;i<row;i++) {
  //   const step= (i === 0 || i === row-1) ? 1 : col-1
  //   for(let j=0;j<col;j+=step) {
  //     dfs(i,j)
  //   }
  // }

  for (let i = 0; i < row; i++) {
    for (let j = 0; j < col; j++) {
      if (grid[i][j] === 1) {
        ret = Math.max(dfs(i, j), ret)
      }
    }
  }
  return ret
}