-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathBrokenBoardDominoesV1.js
More file actions
98 lines (83 loc) · 3.38 KB
/
BrokenBoardDominoesV1.js
File metadata and controls
98 lines (83 loc) · 3.38 KB
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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
// https://leetcode-cn.com/problems/broken-board-dominoes/
var Test = require('./Common/Test');
var Matrix = require('./Common/Matrix').Matrix;
var domino = function (n, m, broken) {
const offsets = [[-1, 0], [0, -1], [1, 0], [0, 1]];
// const offsets = [[1, 0], [0, 1]];
// const offsets = [[-1, 0], [0, -1], [1, 0], [0, 1], [0, 0]];
// for (let y = 0; y < n; y += 2) {
// for (let x = 0; x < m; x += 2) {
// }
// }
// const board = Array(n).fill().map((_, i) => Array(m).fill());
const board = Array(n).fill().map((_, i) => Array(m).fill('.'));
// broken.forEach(([i, j]) => board[i][j] = '#');
broken.forEach(([i, j]) => { if (i < n && j < m) board[i][j] = '#' });
Matrix.logMatrixInArray(board);
// console.log(board);
let max = 0;
backtracking(0, 0, 0);
return max;
function backtracking(x, y, count) {
if (y >= n) {
max = Math.max(max, count);
}
else {
// if (condition) {
// }
// board[y][x] = '#';
// const [nx, ny] = x + 2 < m ? [x + 2, y] : [0, y + 2];
const [nx, ny] = x + 2 < m ? [x + 2, y] : [y % 2 == 1 ? 0 : 1, y + 1];
// console.log({ nx, ny });
// const [nx, ny] = x + 1 < m ? [x + 1, y] : [0, y + 1];
const tryNext = (inc) => backtracking(nx, ny, count + (inc ? 1 : 0));
if (board[y][x] != '#') {
// board[y][x] = '#';
// board[y][x] = '#';
for (const [ox, oy] of offsets) {
const [bx, by] = [x + ox, y + oy];
if (bx >= 0 && bx < m && by >= 0 && by < n) {
if (board[by][bx] != '#') {
board[by][bx] = '#';
tryNext(true);
board[by][bx] = '.';
}
// else {
// }
}
}
// board[y][x] = '.';
}
tryNext(false);
}
}
};
function showBoard(n, m, broken) {
console.log(broken.length);
const board = Array(n).fill().map((_, i) => Array(m).fill().map((_, j) => (i + j) % 2));
broken.forEach(([i, j]) => board[i][j] = '#');
// return Matrix.matrixToString(a);
// Matrix.logMatrixInString(board);
Matrix.logMatrixInArray(board);
}
function test(n, m, broken) {
showBoard(n, m, broken);
const test = new Test.Test(domino, n, m, broken);
// const test = new Test.Test(showBoard, n, m, broken);
// test.logArgs = false;
test.do();
}
// test(2, 3, [[1, 0], [1, 1]]);
// test(3, 3, []);
test(8, 8, [[0, 0], [0, 4], [0, 7], [1, 2], [2, 1], [2, 2], [3, 0], [3, 3], [3, 4], [4, 0], [4, 3], [4, 7], [5, 0], [5, 1], [5, 2], [5, 3], [5, 7], [6, 2], [6, 3], [6, 6], [6, 7], [7, 0], [7, 1], [7, 3], [7, 4]]);
// test(4, 4, [[0, 0], [0, 4], [0, 7], [1, 2], [2, 1], [2, 2], [3, 0], [3, 3], [3, 4], [4, 0], [4, 3], [4, 7], [5, 0], [5, 1], [5, 2], [5, 3], [5, 7], [6, 2], [6, 3], [6, 6], [6, 7], [7, 0], [7, 1], [7, 3], [7, 4]]);
// test(4, 4, [[0, 0], [1, 2], [2, 1], [2, 2], [3, 0], [3, 3]]);
// 2
// 3
// [[1, 0], [1, 1]]
// 3
// 3
// []
// 8
// 8
// [[0, 0], [0, 4], [0, 7], [1, 2], [2, 1], [2, 2], [3, 0], [3, 3], [3, 4], [4, 0], [4, 3], [4, 7], [5, 0], [5, 1], [5, 2], [5, 3], [5, 7], [6, 2], [6, 3], [6, 6], [6, 7], [7, 0], [7, 1], [7, 3], [7, 4]]