leetcode/200.js at master · SambacFeng/leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
/**
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function (grid) {
    let res = 0
    for (let i = 0; i < grid.length; i++) {
        for (let j = 0; j < grid[0].length; j++) {
            if (grid[i][j] === "1") {
                let q = []
                q.push([i, j])
                grid[i][j] = "0"
                while (q.length) {
                    let loc = q.shift()
                    if (loc[0] > 0 && grid[loc[0] - 1][loc[1]] === "1") {
                        q.push([loc[0] - 1, loc[1]])
                        grid[loc[0] - 1][loc[1]] = "0"
                    }
                    if (loc[0] < grid.length - 1 && grid[loc[0] + 1][loc[1]] === "1") {
                        q.push([loc[0] + 1, loc[1]])
                        grid[loc[0] + 1][loc[1]] = "0"
                    }
                    if (loc[1] > 0 && grid[loc[0]][loc[1] - 1] === "1") {
                        q.push([loc[0], loc[1] - 1])
                        grid[loc[0]][loc[1] - 1] = "0"
                    }
                    if (loc[1] < grid[0].length - 1 && grid[loc[0]][loc[1] + 1] === "1") {
                        q.push([loc[0], loc[1] + 1])
                        grid[loc[0]][loc[1] + 1] = "0"
                    }
                }
                res++
            }
        }
    }
    return res
}

/*
    2021/9/12
    35 27
    dfs遍历，遍历到的置为0
    遍历每一个位置，是岛屿的话(面积不为0)res+1
    数组元素类型是字符串。。

    let res = 0

    const dfs = (m, n) => {

        if (m < 0 || m >= grid.length || n < 0 || n >= grid[0].length) return 0
        if (grid[m][n] === '0') return 0
        let area = 0
        grid[m][n] = '0'
        area = 1 + dfs(m - 1, n)
            + dfs(m + 1, n)
            + dfs(m, n - 1)
            + dfs(m, n + 1)
        return area
    }

    for (let i = 0; i < grid.length; i++) {
        for (let j = 0; j < grid[0].length; j++) {
            if (dfs(i, j)) {
                res++
            }
        }
    }

    return res

    2021/9/26
    更新bfs解法
    18 10
*/

let grid = [
    ["1", "1", "1", "1", "0"],
    ["1", "1", "0", "1", "0"],
    ["1", "1", "0", "0", "0"],
    ["0", "0", "0", "0", "0"]
]
numIslands(grid)