-
Notifications
You must be signed in to change notification settings - Fork 0
/
script.js
52 lines (40 loc) · 1.16 KB
/
script.js
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
"use strict";
// graph problem (number of islands)
const islandCount = (grid) => {
const visited = new Set();
let count = 0;
for (let r = 0; r < grid.length; r++) {
for (let c = 0; c < grid[0].length; c++) {
if(explore(grid, r, c, visited)) {
count += 1;
}
}
}
return count;
}
const explore = (grid, row, column, visited) => {
// check if in bounds
const rowInbounds = 0<=row && row<grid.length;
const colummnInbounds = 0<=column && column<grid[0].length;
if(!rowInbounds || !colummnInbounds) return false;
// check if on water
if(grid[row][column] === 'w') return false;
// check if visited
const pos = row+','+column;
if(visited.has(pos)) return false;
visited.add(pos);
explore(grid, row-1, column, visited); // go up
explore(grid, row+1, column, visited); // go down
explore(grid, row, column-1, visited); // go left
explore(grid, row, column+1, visited); // go right
return true;
}
const grid = [
['w', 'L', 'w', 'w', 'w'],
['w', 'L', 'w', 'w', 'w'],
['L', 'w', 'w', 'L', 'w'],
['w', 'w', 'L', 'L', 'w'],
['L', 'w', 'w', 'L', 'L'],
['L', 'L', 'w', 'w', 'w']
]
console.log(islandCount(grid));