-
Notifications
You must be signed in to change notification settings - Fork 3
/
index.js
84 lines (77 loc) · 1.8 KB
/
index.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
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
83
84
/**
* @param {number[][]} grid
* @return {number}
*/
var orangesRotting = function(grid) {
const orangeMaps = getOrangePositionsByType(1);
let orange1Count = orangeMaps[1].length;
if(orange1Count === 0) {
return 0;
}
const res = bfs(orangeMaps[2], 0);
return orange1Count === 0 ? res : -1;
function getOrangePositionsByType() {
const res = {
0: [],
1: [],
2: []
};
grid.forEach((row, i) => {
row.forEach((orange, j) => {
res[orange].push({i, j});
})
});
return res;
}
function bfs(nodes, depth) {
if (nodes.length === 0) {
return depth - 1;
}
const nextNodes = [];
nodes.forEach(({i, j}) => {
nextNodes.push(...spread(i, j));
});
orange1Count -= nextNodes.length;
return bfs(nextNodes, depth + 1);
}
function spread(i, j) {
const spreadNodes = [];
if (i - 1 >= 0) {
if (grid[i - 1][j] === 1) {
grid[i - 1][j] = 2;
spreadNodes.push({i: i - 1, j});
}
}
if (i + 1 < grid.length) {
if (grid[i + 1][j] === 1) {
grid[i + 1][j] = 2;
spreadNodes.push({i: i + 1, j});
}
}
if (j - 1 >= 0) {
if (grid[i][j - 1] === 1) {
grid[i][j - 1] = 2;
spreadNodes.push({i, j: j - 1});
}
}
if (j + 1 < grid[0].length) {
if (grid[i][j + 1] === 1) {
grid[i][j + 1] = 2;
spreadNodes.push({i, j: j + 1});
}
}
return spreadNodes;
}
};
const test1 = [[2,1,1],[1,1,0],[0,1,1]];
const test2 = [[2,1,1],[0,1,1],[1,0,1]];
const test3 = [[0,2]];
console.log(orangesRotting(test1));
console.log(orangesRotting(test2));
console.log(orangesRotting(test3));
module.exports = {
id:'994',
title:'Rotting Oranges',
url:'https://leetcode.com/problems/rotting-oranges/',
difficulty:'easy',
}