Reach the last cell in the least time

Moderate
0/80
Average time to solve is 15m
6 upvotes
Asked in companies
CIS - Cyber InfrastructureAmazonVisa

Problem statement

You are given an ‘N x N’ matrix ‘GRID’. Initially, every cell is locked, and ‘GRID[i][j]’ represents the time at which the cell at ‘(i, j)’ will unlock. You can move from one cell to another 4-dimensionally adjacent cell if and only if both cells are unlocked. You can move through infinite cells in zero time. Also, you cannot leave the boundaries of the grid.

If you start at the cell ‘(0, 0)’, what is the least time required to reach the last cell ‘(N - 1, N - 1)’.

Example: 
‘GRID’ =

example

We cannot reach the cell ‘(2, 2)’ until the time is ‘5’. When the time is ‘5’, we move along the path: 
0 -> 1 -> 4 -> 3 -> 5

The cell with value ‘1’ will be unlocked when the time is ‘1’.
At time = 1: 0 -> 1

Similarly, the cell with value ‘4’ is unlocked when the time is ‘4’. At that time the cell with value ‘3’ will also be unlocked, as it unlocks at time ‘3’.    
At time = 4: 0 -> 1 -> 4 -> 3

The cell with value ‘5’ will be unlocked when the time is ‘5’.
At time = 5: 0 -> 1 -> 4 -> 3 -> 5

So, the least time to reach cell ‘(2, 2)’ is ‘5’.
Note: 
1. All elements in the ‘GRID’ are unique.

2. ‘GRID[i][j]’ is a permutation of [0, 1, … , (N ^ 2) - 1].
Detailed explanation ( Input/output format, Notes, 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 an integer ‘N’ denoting the number of rows and columns in ‘GRID’. Then, ‘N’ lines follow.

Each line contains ‘N’ space-separated integers denoting the row values of ‘GRID’.
Output format: 
For every test case, print a single line containing a single integer denoting the least time required to reach the cell ‘(N - 1, N - 1)’.

The output of each test case will be printed in a separate line.

Note:

You do not need to input or print anything, as it has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 10
2 <= N <= 50
0 <= Value in each element of ‘GRID’ <= (N ^ 2) - 1

Where ‘T’ is the number of test cases, and ‘N’ is the number of rows and columns in ‘GRID’.

Time limit: 1 second

Sample input 1:

2
4
3 4 15 14 
12 0 10 9 
11 8 7 6 
13 5 2 1 
2
0 1 
2 3

Sample output 1:

8
3

Explanation of sample input 1:

Test Case 1:
‘grid’ =

sample1

We cannot reach the cell ‘(3, 3)’ until the time is ‘8’. When the time is ‘8’, we move along the path:
3 -> 4 -> 0 -> 8 -> 5 -> 2 -> 1
So, the least time to reach ‘(3, 3)’ is ‘8’.

Test Case 2:
‘grid’ =

sample2

We cannot reach the cell ‘(1, 1)’ until the time is ‘3’. When the time is ‘3’, we move along the path:
2 -> 1 -> 3
So, the least time to reach ‘(1, 1)’ is ‘3’.

Sample input 2:

2
3
8 7 4
0 6 5
1 2 3
3
1 2 6
7 4 8
5 3 0

Sample output 2:

8
4
Hint

Try to find if we can reach the cell ‘(N - 1, N - 1)’ for all possible time values.

Approaches (3)
Brute force using Breadth-first search

A simple approach will be to assume the time required to reach ‘(n - 1, n - 1)’ as ‘0’. Now traverse the grid from ‘(0, 0)’ and see if we can reach the last cell. If we cannot reach the last cell, then increment the time required by ‘1’ and keep increasing the time until we can reach the last cell. Following is an implementation using BFS traversal:

 

  • Set ‘time = 0’. Use this to store the time required to reach the last cell ‘(n - 1, n - 1)’.
  • Run a loop until ‘bfs(time)’ is not equal to true:
    • ‘time += 1’. We increase the time so that more cells are unlocked and again try to reach the last node.
  • Return ‘time’ as the answer.

 

The ‘bfs(integer time)’ function:

  • Create a 2-d array ‘seen[n][n]’ with each element set to ‘false’. Use it to mark the visited cells in the BFS traversal.
  • Create a queue ‘bfsQ’. Use it to perform the BFS traversal.
  • Initialize ‘dir[4][2] = [(1, 0), (-1, 0), (0, 1), (0, -1)]. Add ‘dir[i]’ to a cell to move to an adjacent cell.
  • Push ‘(0, 0)’ in ‘bfsQ’ and set ‘seen[0][0] = true’ (the source node).
  • Run a loop until ‘bfsQ’ is not empty:
    • ‘(x, y) = bfsQ.pop()’. Get the location of the cell in front of the queue and pop it.
    • Run a loop where ‘i’ ranges from ‘0’ to ‘3’:
      • ‘newX = x + dir[i][0]’ and ‘newY = y + dir[i][0]’. The location of adjacent cell.
      • If (‘(newX, newY)’ is a valid cell) and (‘seen[newX][newY]’ is false) and (‘grid[newX][newY] <= time’), then the adjacent cell is valid and reachable from ‘(x, y)’:
        • If ‘newX = n - 1’ and ‘newY = n - 1’, then we have reached the last cell:
          • Return true.
        • ‘seen[newX][newY] = true’
        • Push ‘(newX, newY)’ in ‘bfsQ’.
  • Return false, as we were unable to reach the last cell.
Time Complexity

O(N ^ 4), where ‘N’ is the number of rows and columns in ‘grid’.

 

In the worst-case scenario, the time required to reach the last cell is ‘(N ^ 2) - 1’, so we call the ‘bfs’ function ‘O(N ^ 2)’ times. The BFS traversal visits every cell once, taking ‘O(N ^ 2)’ time. Hence, the total time complexity is ‘O(N ^ 4)’

Space Complexity

O(N ^ 2), where ‘n’ is the number of rows and columns in ‘grid’.

 

The ‘seen’ matrix requires ‘O(N ^ 2)’ space, and the ‘bfsQ’ stores ‘O(N ^ 2)’ cells in the worst-case scenario.

Code Solution
(100% EXP penalty)
Reach the last cell in the least time
Full screen
Console