Grid Traversal
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.
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
The optimal path is:
- From (0, 0) jump to (0, 3). Since we jumped a length of 3, 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.
Constraints
Limits and guarantees your solution can rely on.
2 ≤ n, m ≤ 100