-
Notifications
You must be signed in to change notification settings - Fork 0
/
surrounded-regions.js
58 lines (48 loc) · 1.44 KB
/
surrounded-regions.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
// https://leetcode.com/problems/surrounded-regions/
/**
* @param {character[][]} board
* @return {void} Do not return anything, modify board in-place instead.
*/
const canBeCaptured = (board, row, c, g = [], v = {}) => {
if (v[`${row}-${c}`]) return v[`${row}-${c}`];
v[`${row}-${c}`] = true;
if (row > board.length-1 ||
row < 0 ||
c > board[0].length-1 ||
c < 0) {
return true;
}
if (row === board.length-1 ||
row === 0 ||
c === board[0].length-1 ||
c === 0) {
return board[row][c] === 'X';
}
if (board[row][c] === 'X') {
return true;
}
g.push({row, c});
return canBeCaptured(board, row-1, c, g, v) &&
canBeCaptured(board, row+1, c, g, v) &&
canBeCaptured(board, row, c-1, g, v) &&
canBeCaptured(board, row, c+1, g, v);
};
const markVisitedWell = (board, regions) => {
regions.forEach((region) => {
board[region.row][region.c] = 'X';
});
};
const solve = function(board) {
for(let row=0; row<board.length; row++){
for(let c=0; c<board[0].length; c++){
if (board[row][c] === 'O') {
const g = [];
const canBe = canBeCaptured(board, row, c, g);
if (canBe) {
board[row][c] = 'X';
markVisitedWell(board, g)
}
}
}
}
};