跟着卡哥学算法Day 51：图论part2 岛屿问题

1
function numIslands(grid) {
2
  if (!grid?.length) return 0
3

4
  const rows = grid.length
5
  const cols = grid[0].length
6

7
  const directions = [
8
    [0, 1],
9
    [1, 0],
10
    [0, -1],
11
    [-1, 0],
12
  ]
13
  const visited = new Array(rows).fill().map(() => new Array(cols).fill(false)) // 用于标记哪些节点已经访问过，避免重复访问
14

15
  let isLandCount = 0
16

17
  // 递归访问当前节点的所有相邻陆地节点
18
  const dfs = (x, y) => {
19
    // 每次递归调用时，标记当前节点为已访问
20
    visited[x][y] = true
21

22
    for (const [dx, dy] of directions) {
23
      const nextX = dx + x
24
      const nextY = dy + y
25
      if (
26
        nextX >= 0 &&
27
        nextX < rows &&
28
        nextY >= 0 &&
29
        nextY < cols &&
30
        !visited[nextX][nextY] &&
31
        grid[nextX][nextY] === '1'
32
      ) {
33
        dfs(nextX, nextY)
34
      }
35
    }
36
  }
37
  for (let i = 0; i < rows; i++) {
38
    for (let j = 0; j < cols; j++) {
39
      if (!visited[i][j] && grid[i][j] === '1') {
40
        isLandCount++
41
        dfs(i, j)
42
      }
43
    }
44
  }
45
  return isLandCount
46
}

1
const r1 = require('readline').createInterface({ input: process.stdin })
2
// 创建readline接口
3
let iter = r1[Symbol.asyncIterator]()
4
// 创建异步迭代器
5
const readline = async () => (await iter.next()).value
6

7
let graph
8
let N, M
9
let visited
10
let result = 0
11
const dir = [
12
  [0, 1],
13
  [1, 0],
14
  [0, -1],
15
  [-1, 0],
16
]
17

18
// 读取输入，初始化地图
19
const initGraph = async () => {
20
  let line = await readline()
21
  ;[N, M] = line.split(' ').map(Number)
22
  graph = new Array(N).fill(0).map(() => new Array(M).fill(0))
23
  visited = new Array(N).fill(false).map(() => new Array(M).fill(false))
24

25
  for (let i = 0; i < N; i++) {
26
    line = await readline()
27
    line = line.split(' ').map(Number)
28
    for (let j = 0; j < M; j++) {
29
      graph[i][j] = line[j]
30
    }
31
  }
32
}
33

34
/**
35
 * @description: 从节点x,y开始深度优先遍历
36
 * @param {*} graph 是地图，也就是一个二维数组
37
 * @param {*} visited 标记访问过的节点，不要重复访问
38
 * @param {*} x 表示开始搜索节点的下标
39
 * @param {*} y 表示开始搜索节点的下标
40
 * @return {*}
41
 */
42
const dfs = (graph, visited, x, y) => {
43
  for (let i = 0; i < 4; i++) {
44
    const nextx = x + dir[i][0]
45
    const nexty = y + dir[i][1]
46
    if (nextx < 0 || nextx >= N || nexty < 0 || nexty >= M) continue
47
    if (!visited[nextx][nexty] && graph[nextx][nexty] === 1) {
48
      visited[nextx][nexty] = true
49
      dfs(graph, visited, nextx, nexty)
50
    }
51
  }
52
}
53

54
;(async function () {
55
  // 读取输入，初始化地图
56
  await initGraph()
57

58
  // 统计岛屿数
59
  for (let i = 0; i < N; i++) {
60
    for (let j = 0; j < M; j++) {
61
      if (!visited[i][j] && graph[i][j] === 1) {
62
        // 标记已访问
63
        visited[i][j] = true
64

65
        // 遇到没访问过的陆地，+1
66
        result++
67

68
        // 深度优先遍历，将相邻陆地标记为已访问
69
        dfs(graph, visited, i, j)
70
      }
71
    }
72
  }
73
  console.log(result)
74
})()

1
function maxAreaOfIsland(grid) {
2
  if (!grid || grid.length === 0) return 0
3

4
  const rows = grid.length
5
  const cols = grid[0].length
6
  const directions = [
7
    [0, 1], // 右
8
    [1, 0], // 下
9
    [0, -1], // 左
10
    [-1, 0], // 上
11
  ]
12

13
  let maxArea = 0
14

15
  // 深度优先搜索函数
16
  const dfs = (x, y) => {
17
    if (x < 0 || x >= rows || y < 0 || y >= cols || grid[x][y] === 0) {
18
      return 0
19
    }
20

21
    grid[x][y] = 0 // 标记为已访问
22
    let area = 1 // 当前节点的面积为 1
23

24
    for (const [dx, dy] of directions) {
25
      area += dfs(x + dx, y + dy) // 累加相邻陆地的面积
26
    }
27

28
    return area
29
  }
30

31
  // 遍历整个网格
32
  for (let i = 0; i < rows; i++) {
33
    for (let j = 0; j < cols; j++) {
34
      if (grid[i][j] === 1) {
35
        const area = dfs(i, j) // 计算当前岛屿的面积
36
        maxArea = Math.max(maxArea, area) // 更新最大面积
37
      }
38
    }
39
  }
40

41
  return maxArea
42
}