Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit5668e64

Browse files
authored
algorithm: unique paths 2 (TheAlgorithms#1257)
* algorithm: add UniquePaths2 algo and a test for it* fix: fix inaccuracies and spelling errors
1 parentc39d666 commit5668e64

File tree

2 files changed

+95
-0
lines changed

2 files changed

+95
-0
lines changed

‎Dynamic-Programming/UniquePaths2.js

Lines changed: 76 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,76 @@
1+
/*
2+
* Unique Paths 2
3+
*
4+
* There is a robot on an `m x n` grid.
5+
* The robot is initially located at the top-left corner
6+
* The robot tries to move to the bottom-right corner.
7+
* The robot can only move either down or right at any point in time.
8+
*
9+
* Given grid with obstacles
10+
* An obstacle and space are marked as 1 or 0 respectively in grid.
11+
* A path that the robot takes cannot include any square that is an obstacle.
12+
* Return the number of possible unique paths that the robot can take to reach the bottom-right corner.
13+
*
14+
* More info: https://leetcode.com/problems/unique-paths-ii/
15+
*/
16+
17+
/**
18+
*@description Return 'rows x columns' grid with cells filled by 'filler'
19+
*@param {Number} rows Number of rows in the grid
20+
*@param {Number} columns Number of columns in the grid
21+
*@param {String | Number | Boolean} filler The value to fill cells
22+
*@returns {Array [][]}
23+
*/
24+
constgenerateMatrix=(rows,columns,filler=0)=>{
25+
constmatrix=[]
26+
for(leti=0;i<rows;i++){
27+
constsubmatrix=[]
28+
for(letk=0;k<columns;k++){
29+
submatrix[k]=filler
30+
}
31+
matrix[i]=submatrix
32+
}
33+
returnmatrix
34+
}
35+
36+
/**
37+
*@description Return number of unique paths
38+
*@param {Array [][]} obstacles Obstacles grid
39+
*@returns {Number}
40+
*/
41+
constuniquePaths2=(obstacles)=>{
42+
if(!Array.isArray(obstacles)){
43+
thrownewError('Input data must be type of Array')
44+
}
45+
// Create grid for calculating number of unique ways
46+
constrows=obstacles.length
47+
constcolumns=obstacles[0].length
48+
constgrid=generateMatrix(rows,columns)
49+
// Fill the outermost cell with 1 b/c it has
50+
// the only way to reach neighbor
51+
for(leti=0;i<rows;i++){
52+
// If robot encounters an obstacle in these cells,
53+
// he cannot continue moving in that direction
54+
if(obstacles[i][0]){
55+
break
56+
}
57+
grid[i][0]=1
58+
}
59+
for(letj=0;j<columns;j++){
60+
if(obstacles[0][j]){
61+
break
62+
}
63+
grid[0][j]=1
64+
}
65+
// Fill the rest of grid by dynamic programming
66+
// using following reccurent formula:
67+
// K[i][j] = K[i - 1][j] + K[i][j - 1]
68+
for(leti=1;i<rows;i++){
69+
for(letj=1;j<columns;j++){
70+
grid[i][j]=obstacles[i][j] ?0 :grid[i-1][j]+grid[i][j-1]
71+
}
72+
}
73+
returngrid[rows-1][columns-1]
74+
}
75+
76+
export{uniquePaths2}
Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
import{uniquePaths2}from'../UniquePaths2'
2+
3+
describe('Unique Paths2',()=>{
4+
// Should return number of ways, taken into account the obstacles
5+
test('There are obstacles in the way',()=>{
6+
expect(uniquePaths2([[0,0,0],[0,1,0],[0,0,0]])).toEqual(2)
7+
expect(uniquePaths2([[0,0,0],[0,1,0],[0,0,0],[1,0,0]])).toEqual(3)
8+
})
9+
// Should return number of all possible ways to reach right-bottom corner
10+
test('There are no obstacles in the way',()=>{
11+
expect(uniquePaths2([[0,0,0],[0,0,0],[0,0,0]])).toEqual(6)
12+
expect(uniquePaths2([[0,0,0],[0,0,0]])).toEqual(3)
13+
})
14+
// Should throw an exception b/c input data has wrong type
15+
test('There are wrong type of input data',()=>{
16+
expect(()=>uniquePaths2('wrong input')).toThrow()
17+
expect(()=>uniquePaths2(100)).toThrow()
18+
})
19+
})

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp