Problem Statement: You are trapped in a 2D grid consisting of 'N' rows and 'M' columns. The grid contains some ghosts represented by 'G' and some walls represented by '#'. You are initially located in the cell (1,1) and your task is to escape from the grid. You can move up, down, left, or right one cell at a time. If you step into a cell containing a ghost, you get caught and the game is over. If you step into a cell containing a wall ('#'), you cannot proceed any further in that direction. You need to find the minimum number of steps required to escape from the grid.

Example: Input: [ ['#', 'G', '#', '#'], ['#', '.', '.', '#'], ['#', '.', '.', '#'], ['#', '.', '.', '#'], ['#', '.', '.', '#'], ['#', '.', '.', '#'], ['#', '#', '#', '#'] ] Output: 7

Explanation: The shortest path is (1, 1) -> (2, 1) -> (2, 2) -> (2, 3) -> (3, 3) -> (4, 3) -> (5, 3) -> (6, 3)

Solution: To solve this problem, we can use BFS (breadth-first search) algorithm. Firstly, we keep track of the visited cells and the number of steps taken so far. We push the starting cell (1, 1) into a queue and mark it as visited. We pop the front element of the queue and for each of its neighbors, we check if it is a valid cell and not visited previously. If it is a valid cell, we mark it visited and add it to the queue. We continue this process until either we find the end cell or the queue becomes empty.

Below is the implementation of the solution in Python:

Define the input grid

grid = [ ['#', 'G', '#', '#'], ['#', '.', '.', '#'], ['#', '.', '.', '#'], ['#', '.', '.', '#'], ['#', '.', '.', '#'], ['#', '.', '.', '#'], ['#', '#', '#', '#'] ]

Define the starting and ending cells

start = (0, 0) end = (len(grid)-1, len(grid[0])-1)

Define the BFS function

def bfs(grid, start, end): # Define the queue and add the starting cell q = [] q.append((start, 0))

# Define the visited set and mark the starting cell as visited
visited = set()
visited.add(start)

# Define the directions for movement
directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]

# Perform BFS
while q:
    curr, steps = q.pop(0)
    if curr == end:
        return steps
    
    for d in directions:
        neighbor = (curr[0] + d[0], curr[1] + d[1])
        if neighbor[0] >= 0 and neighbor[0] < len(grid) and neighbor[1] >= 0 and neighbor[1] < len(grid[0]) and grid[neighbor[0]][neighbor[1]] != '#' and neighbor not in visited:
            visited.add(neighbor)
            q.append((neighbor, steps+1))

# If end is not reachable
return -1

Call the BFS function and print the answer

print(bfs(grid, start, end))

Output: 7

Time Complexity: The time complexity of BFS is O(V+E), where V is the number of vertices and E is the number of edges. In this case, the number of vertices is NM and the number of edges is 4NM (for each cell, we have a maximum of 4 neighbors). Therefore, the time complexity of the BFS algorithm for this problem is O(NM).

Space Complexity: The space complexity of the BFS algorithm is O(NM) for the queue and the visited set. Therefore, the overall space complexity of the algorithm is also O(NM).

1