Problem Statement :
Ninja was supposed to go on a road trip with his friends, but his car was damaged. Ninja wants to repair it as soon as possible. Help ninja to find the nearest service station. You are given a character matrix, ‘grid’ of size ‘n x m’. The ‘grid’ contains the following characters:
- ’N’ represents the ninja’s location. There is exactly one cell with the character ’N’ in it.
- ‘S’ represents a service station. The ‘grid’ can have multiple ‘S’ cells (>= 0).
- ‘O’ is a free space, and the ninja can travel through these cells
- ‘X’ is an obstacle, and the ninja cannot travel through these cells.
The ninja can only travel to adjacent free cells from his current location, i.e., in the North, South, East, or West direction. Your task is to find the length of the shortest path through which the ninja can get to a service station. If there is no such path available, return -1.
Sample Input :
5 8
X X X X X X X X
X N O X O O S X
X O O X O X X X
X O O O O O S X
X X X X X X X XSample Output :
7Approach :
Use Breadth-first search algorithm
Since the given grid can be considered as an unweighted graph, we can find the shortest path for each node in O(E + V) = O(m * n) time using a modified Breadth-first search algorithm. The shortest path length will be equivalent to the node’s level in the BFS traversal tree.
Proof of correctness: As we move level-wise in BFS, if a child node is not visited, it’s not reachable from any previous levels. Its shortest path will be equal to (parent node’s level + 1). Even if it’s reachable from any other node from the next levels, the corresponding path length will always be greater.
Following is a BFS implementation to solve this problem:
Time Complexity : O(M*N)
Space Complexity : O(M*N)
