Meesho SDE 1 | Online Assessment Question

I got three questions in Meesho Online Assesment with 120 minutes as time limit. Was Able to Solve 2 of them.Difficulty is Medium , Medium, Med-Hard. Need Help to UPSolve Third Problem

Q3 Statement: Minimum Jumps to Reach the Endpoint

You are given a grid of size ( n * m ) represented as a vector of strings. Each cell in the grid can have one of the following characters:

• 'S': The starting point. There is exactly one 'S' in the grid.
• 'E': The endpoint. There is exactly one 'E' in the grid.
• '*': An empty cell through which you can jump.
• '#': A blocked cell that you cannot traverse.

Your task is to determine the minimum number of jumps required to move from the starting point 'S' to the endpoint 'E'. A jump is defined as follows:

1. You can jump in any of the four cardinal directions (up, down, left, or right) by covering any distance k , where ( k >= 1).
2. You must continue jumping in the same direction unless your previous jump was of length ( 1 ). After a jump of length ( 1 ), you are allowed to change direction and jump in a new direction with any length ( k ).
3. You cannot land on or jump through blocked cells ('#'), and you cannot jump outside the bounds of the grid.

Input

2. A vector of ( n ) strings, each of length ( m ), representing the grid.

Output

• Return the minimum number of jumps required to reach the endpoint 'E' from the starting point 'S'. If it is impossible to reach 'E', return -1.

Example

Input:

3
S***
###*
###E

Output:

3

Explanation:

1. Start at (0, 0) ('S') and jump right to (0, 3) (first jump).
2. Change direction and jump down to (0, 4) (second jump).
3. Continue jumping down to (2, 4) ('E') (third jump).