BackmediumBacktracking TCS

Avoiding Asteroids in Space Travel Solution

Problem Statement

Given a 7x9 grid representing space and a list of asteroid coordinates, find all unique paths from the top-left corner to the bottom-right corner without hitting an asteroid. Movement is restricted to either down or right at any point.

Example 1
Input
[[0,0,0,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,0,0]]
Output
1

Explanation: Step-by-step: with input [[0,0,0,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,0,0]], we start at the top-left corner and move right until we hit the asteroid at [0,1]. We then backtrack and move down until we reach the bottom-right corner, giving output 1.

Example 2
Input
[[0,0,0,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,1,0]]
Output
0

Explanation: Step-by-step: with input [[0,0,0,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,1,0]], we start at the top-left corner and move right until we hit the asteroid at [0,1]. We then backtrack and move down until we reach the bottom-right corner, but we hit the asteroid at [6,8] which blocks the path, giving output 0.

Constraints

  • 1 <= m, n <= 20
  • 0 <= number of asteroids <= 10

More Backtracking Problems

Protocol Tome Tracker 4easyNode Matrix Optimizer 8easyNetwork Node Architect 13easyProtocol Pipeline Detector 18easy
View all problems →
Live Compiler
Loading...
Test Cases & Output
🔒 Sign up to run your code

🚀 Practice this problem

Run code, get AI hints & track streak

Sign Up Free