/
index.ts
65 lines (60 loc) · 1.63 KB
/
index.ts
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
export default function maxAreaOfIsland(grid: number[][]): number {
const m = grid.length;
if (m === 0) return 0;
const n = grid[0].length;
if (n === 0) return 0;
return Math.max(...getIslandsAreas(grid), 0);
}
function getIslandsAreas(grid: number[][]): number[] {
const m = grid.length;
if (m === 0) return [];
const n = grid[0].length;
if (n === 0) return [];
const cache = new Set<number>();
const islandareas: Array<number> = [];
for (let r = 0; r < m; ++r) {
for (let c = 0; c < n; ++c) {
if (cache.has(unique_id(r, c, n))) {
continue;
}
if (grid[r][c] == 1) {
// ++num_islands;
let islandarea = 0;
dfs(grid, r, c, cache, () => islandarea++);
islandareas.push(islandarea);
}
}
}
// console.log(islands)
return islandareas;
}
function dfs(
grid: number[][],
r: number,
c: number,
cache: Set<number>,
output: () => void,
): void {
const m = grid.length;
if (m === 0) return;
const n = grid[0].length;
if (n === 0) return;
if (r < 0 || c < 0 || r >= m || c >= n || grid[r][c] == 0) {
return;
}
const id = unique_id(r, c, n);
if (cache.has(id)) {
return;
}
cache.add(id);
output();
dfs(grid, r - 1, c, cache, output);
dfs(grid, r + 1, c, cache, output);
dfs(grid, r, c - 1, cache, output);
dfs(grid, r, c + 1, cache, output);
}
function unique_id(r: number, c: number, n: number): number {
const a = c + r * n;
// console.log(c, r, n, a)
return a;
}