Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Shortest Path in a Grid with Obstacles Elimination
Bookmark
BFS with State Tracking
A* Search
Input
Example 1
Example 2
Small easy
Manhattan shortcut
Custom
grid
=
[[0,0,0],[1,1,0],[0,0,0],[0,1,1],[0,0,0]]
,
k
=
1
0
0
0
1
1
0
0
0
0
0
1
1
0
0
0
queue
Open
Obstacle
Visited
Eliminated
0
0
0
1
1
0
0
0
0
0
1
1
0
0
0
queue
Open
Obstacle
Visited
Eliminated
0
0
0
1
1
0
0
0
0
0
1
1
0
0
0
(0,2) k1
(1,1) k0
front
rear
queue
Open
Obstacle
Visited
Eliminated
0
0
0
1
1
0
0
0
0
0
1
1
0
0
0
(2,0) k0
(0,0) k0
(1,2) k1
(1,2) k0
front
rear
queue
Open
Obstacle
Visited
Eliminated
0
0
0
1
1
0
0
0
0
0
1
1
0
0
0
(1,2) k1
(1,2) k0
(2,1) k0
(0,1) k0
(3,0) k0
front
rear
queue
Open
Obstacle
Visited
Eliminated
0
0
0
1
1
0
0
0
0
0
1
1
0
0
0
(0,1) k0
(3,0) k0
(2,2) k1
(2,2) k0
(0,2) k0
front
rear
queue
Open
Obstacle
Visited
Eliminated
0
0
0
1
1
0
0
0
0
0
1
1
0
0
0
(2,2) k1
(2,2) k0
(0,2) k0
(4,0) k0
front
rear
queue
Open
Obstacle
Visited
Eliminated
0
0
0
1
1
0
0
0
0
0
1
1
0
0
0
(4,0) k0
(2,1) k1
(3,2) k0
front
rear
queue
Open
Obstacle
Visited
Eliminated
0
0
0
1
1
0
0
0
0
0
1
1
0
0
0
(3,2) k0
(4,1) k0
(2,0) k1
front
rear
queue
Open
Obstacle
Visited
Eliminated
0
0
0
1
1
0
0
0
0
0
1
1
0
0
0
(2,0) k1
(3,1) k0
(4,2) k0
front
rear
queue
Open
Obstacle
Visited
Eliminated
0
0
0
1
1
0
0
0
0
0
1
1
0
0
0
queue
Open
Obstacle
Visited
Eliminated
algo
master
.
io
Step:
Start: shortest path from (0, 0) to (4, 2) removing at most 1 obstacle
0 / 194
Input
Example 1
Example 2
Small easy
Manhattan shortcut
Custom
grid
=
[[0,0,0],[1,1,0],[0,0,0],[0,1,1],[0,0,0]]
,
k
=
1
0 / 194
algo
master
.
io
Step:
Start: shortest path from (0, 0) to (4, 2) removing at most 1 obstacle
