Repository navigation
Expand file tree
/
Copy pathbtUniquePaths.js
More file actions
58 lines (49 loc) 路 1.74 KB
/
Copy pathbtUniquePaths.js
File metadata and controls
58 lines (49 loc) 路 1.74 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
/**
* BACKTRACKING approach of solving Unique Paths problem.
*
* @param {number} width - Width of the board.
* @param {number} height - Height of the board.
* @param {number[][]} steps - The steps that have been already made.
* @param {number} uniqueSteps - Total number of unique steps.
* @return {number} - Number of unique paths.
*/
export default function btUniquePaths(width, height, steps = [[0, 0]], uniqueSteps = 0) {
// Fetch current position on board.
const currentPos = steps[steps.length - 1];
// Check if we've reached the end.
if (currentPos[0] === width - 1 && currentPos[1] === height - 1) {
// In case if we've reached the end let's increase total
// number of unique steps.
return uniqueSteps + 1;
}
// Let's calculate how many unique path we will have
// by going right and by going down.
let rightUniqueSteps = 0;
let downUniqueSteps = 0;
// Do right step if possible.
if (currentPos[0] < width - 1) {
steps.push([
currentPos[0] + 1,
currentPos[1],
]);
// Calculate how many unique paths we'll get by moving right.
rightUniqueSteps = btUniquePaths(width, height, steps, uniqueSteps);
// BACKTRACK and try another move.
steps.pop();
}
// Do down step if possible.
if (currentPos[1] < height - 1) {
steps.push([
currentPos[0],
currentPos[1] + 1,
]);
// Calculate how many unique paths we'll get by moving down.
downUniqueSteps = btUniquePaths(width, height, steps, uniqueSteps);
// BACKTRACK and try another move.
steps.pop();
}
// Total amount of unique steps will be equal to total amount of
// unique steps by going right plus total amount of unique steps
// by going down.
return rightUniqueSteps + downUniqueSteps;
}