How should I practice Grid Traversal?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Snowflake online assessment problems in FastPrep.

Is Grid Traversal associated with Snowflake?

FastPrep tags this as a Snowflake online assessment coding practice problem when the problem catalog has that company and stage context.

Problem · Matrix

Grid Traversal

Learn this problem

● Hard

SnowflakeOA

See Snowflake hiring insights

Problem statement

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

getMinJumps(grid: String[]) → int

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'.

Examples

Example 1

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

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.

The total number of jumps required is 5. This is the minimum number of jumps required as well.

Constraints

2 ≤ n, m ≤ 100

Problem statement

Function

Examples

Example 1

Constraints

More Snowflake problems