Problem Brief

Grid Traversal (Infrastructure Automation Internship)

INTERNOA

The city of Hackerland is represented by a grid with n rows and m columns, where empty cells are marked with "*", and blocked cells are marked with '#'. Travel is only possible through empty cells. The inhabitants need to travel from a starting cell marked by 'S' to an ending cell marked by 'E'.

They can jump any integer length k in four directions: up, down, left, and right. If the jump length k is greater than 1, the next jump must continue in the same direction. For example, a hacker can jump 3 units to the right, followed by 1 unit to the right, and then 3 units to the left. However, they cannot jump 3 units to the right followed by 1 unit to the left, as direction changes are not allowed if the previous jump was longer than 1 unit. The last jump in any sequence must always be of length 1. Jumps can be made over blocked cells as long as both the starting and ending cells of the jump are empty.

Given the map of Hackerland as a 2D matrix grid containing exactly one 'S' and one 'E', determine the minimum number of jumps required to travel from 'S' to 'E'. Return -1 if it is not possible.

Function Description

Complete the function getMinJumps in the editor with the following parameter(s):

grid[n][m]: an array of strings

Returns

int: the minimum number of jumps to reach cell 'E' starting from 'S', or -1 if it is not possible

Constraints

2 ≤ n, m ≤ 100

The strings will have only '*', '#', 'S', and 'E'. There will be only one 'S' and one 'E'.

1Example 1

Input

grid = ["S#", "#E"]

Output

-1

Explanation

It is not possible to move to any adjacent cell in the grid.

2Example 2

Input

grid = ["S******", "#######", "######*"]

Output

Explanation

The optimal path is:

Jump from (0, 0) to (0, 5). The next jump needs to be in the same direction.
Jump from (0, 5) to (0, 6).
Jump from (0, 6) to (2, 6). The next jump must be in the same direction.
Jump from (2, 6) to (3, 6). We have reached the destination cell.

Thus, we need 4 moves.

3Example 3

Input

grid = ["S****#", "**#***", "*****#", "*#*#**", "#****E"]

Output

Explanation

The optimal is - From (0, 0), jump to (0, 3). Since we jumped a length of 4, we must make the next jump in the same direction. From (0, 3), jump to (0, 4). Given the jump length was 1, we are allowed to change direction in the next jump. From (0, 4), jump to (3, 4). Again, the next jump must be in the same direction. From (3, 4), jump to (4, 4). We may change the direction for the next jump. From (4, 4), jump to (4, 5). We have reached the destination cell. The total number of jumps required is 5. This is the minimum number of jumps required as well.