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 step-by-step 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 bottom-right 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 bottom-right 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:

 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
def find_path(matrix):
    rows, cols = len(matrix), len(matrix[0])
    obstacles = set()
    superpowers = set()
    
    # Step 1: Collect positions of 'G' and 'S'
    for i in range(rows):
        for j in range(cols):
            if matrix[i][j] == 'G':
                obstacles.add((i, j))
            elif matrix[i][j] == 'S':
                superpowers.add((i, j))

    # Initialize starting point
    i, j = 0, 0
    
    while i < rows and j < cols:
        # Check if we've reached the destination
        if (i, j) == (rows-1, cols-1):
            return True

        # Step 4: Check for superpower and skip row if found
        if (i, j) in superpowers:
            i = i + 1
            continue

        # Check possible directions (right, down, diagonally)
        directions = [(1, 0), (0, 1), (1, 1), (-1, 1), (1, -1), (-1, -1), (-1, 0), (0, -1)]
        
        found = False
        for dx, dy in directions:
            ni, nj = i + dx, j + dy
            if 0 <= ni < rows and 0 <= nj < cols:
                # Step 3: Skip if an obstacle is found
                if (ni, nj) in obstacles:
                    continue
                # Move to the next cell
                i, j = ni, nj
                found = True
                break

        # Step 5: If no path found, return False
        if not found:
            return False

    return False

# Test case
matrix = [
    ['.', '.', '.', 'G', '.', '.'],
    ['A', '.', '.', '.', '.', 'G'],
    ['.', '.', '.', '.', '.', '.'],
    ['.', 'G', '.', '.', '.', '.']
]
print(find_path(matrix))

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