New update is available. Click here to update.

Path to the nearest service station

MEDIUM

15 mins

3 upvotes

Graph

Matrices (2D Arrays)

Solve problems & track your progress

Checkout your overall progress in every topic here

Become

Sensei

in DSA topics

Open the topic and solve more problems associated with it to improve your skills

Check out the skill meter for every topic

See how many problems you are left with to solve for cracking any stage. Score more than zero to get your progress counted.

Problem

Submissions

Path to the nearest service station

Contributed by

Deep Mavani

Medium

0/80

Avg time to solve 15 mins

Success Rate 85 %

3 upvotes

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.

Example:

‘N’ = 4, ‘M’ = 6
Given ‘GRID’:
(Empty cells represent the character ‘O’)

The Ninja can reach the nearest service station by moving two cells south and then three cells east. So, the answer is ‘5’.

Detailed explanation ( Input/output format, Notes, Constraints, Images )

Input format:

The first line of input contains an integer ‘T’ which denotes the number of test cases. Then, the ‘T’ test cases follow.

Each test case’s first line contains two space-separated integers, ‘N’ and ‘M’, denoting the number of rows and columns in the ‘GRID’.

The next ‘N’ lines contain ‘M’ characters denoting the elements of the 'GRID'.

Output format:

For every test case, return the length of the shortest path to a service station. If no such path is available, return -1;

Note:

You do not need to print anything; it has already been taken care of. Just implement the function.

Constraints:

1 <= T <= 10
1 <= N, M <= 100
Value in each element of ‘GRID’ = {‘N’, ‘S’, ‘O’, ‘X’}

Time limit: 1 second

Sample input 1:

2
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 X 
5 6
X X X X X X 
X N O X S X 
X O O X O X 
X O X S O X 
X X X X X X

Sample output 1:

7
-1

Explanation of sample input 1:

Test Case 1:
‘N’ = 5, ‘M’ = 8
Given ‘GRID’:
(Empty cells represent the character ‘O’)

The Ninja can reach the nearest service station by moving two cells south and then five cells east. So, the answer is ‘7’.


Test Case 2:
‘N’ = 5, ‘M’ = 6
Given ‘GRID’:
(Empty cells represent the character ‘O’)

As the Ninja cannot reach any service station because of obstacles, the answer is ‘-1’.

Sample input 2:

2
4 5
X X X X X 
X N O O O 
X O O O S 
X X X X X 
3 4
N O S X 
O O X X 
S O X X

Sample output 2:

4
2

Auto

Console