Finding a Path in a Matrix with Obstacles and Superpower
Given a nxm matrix. Given a character ‘A’ you have tell if there exists a path to reach the right bottom cell. Matrix has some obstacles G you cant cross. you can move in 8 directions. Time complexity should be O(m+n) / O(m*n).
. . . G . . A . . . . G . . . . . . . G . . . .
Optimization: There is a charater S with superpower. If you encounter S you can skip the whole row. Hint: To collect the location of all G and S which will take mn. After that the function to find if path exist can be done in O(m+n)
Solution
To solve this problem, we first collect the locations of all obstacles ‘G’ and superpowers ‘S’. This step takes O(m*n) time complexity. Then, we can determine if there is a path from ‘A’ to the bottom right cell in O(m+n) time.
Here’s a stepbystep plan to solve this:
Traverse the entire matrix to identify the positions of ‘G’ (obstacles) and ‘S’ (superpowers). Store these in separate data structures. Time complexity for this step is O(m*n).
Start from the ‘A’ position and move towards the bottomright corner.
Whenever you encounter an obstacle ‘G’, check if it’s possible to detour.
If you encounter ‘S’, you can skip the entire row, moving directly to the next row at the same column position.
Check if you reach the bottomright corner within the given constraints.
By following these steps, you can solve this problem in O(m+n) time after the initial setup.
Python code:


Note: This code works under the assumption that the starting point ‘A’ is always at matrix[0][0] and the destination is at the bottomright corner. Modify accordingly if that’s not the case.