isPath

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
2 upvotes
Asked in company
Amazon

Problem statement

Ninja is developing robotics delivery. They have a robot standing at the top left corner(0,0) of the matrix of size N*N. It has to deliver the parcel to the given (x,y) coordinate. There are also obstacles at random points in the matrix. The robot cannot enter the coordinate with an obstacle. It can only travel only on flat coordinates. The obstacle is denoted by 0 and the flat is denoted by 1. Matrix[ x ] [ y ] is denoted by 5. You have to return true if it is possible to deliver the package to the given coordinate Else return false. Given robot can move downwards and rightwards from the given coordinate and cannot enter over the obstacle and cannot move outside the matrix. Matrix[ 0 ][ 0 ] is always 1.

For Example : 
Corresponding to the given matrix:-


From (0,0) coordinate robot cannot move to (0,1) 
coordinate since there is obstacle on it.
So to reach (2,2) The path is (0,0) then to (1,0) then to 
(2,0) then to (2,1) and finally (2,2).
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of input contains an integer ‘T’ denoting the number of test cases.
The first line of each test case contains three single-spaced integers N,x,y representing the length and width of the matrix and the coordinates of the delivery location.
The next N line contains N Single-spaced elements (0 or 1 or 5).
Output Format : 
For each test case, return true if there is a path from (0,0) to the (x,y), otherwise, return false.

Output for each query is printed in a separate line.
Constraints : 
1 <= 'T' <= 10
1 <= 'n' <= 100
matrix[ i ][ j ] = {0,1,5}

where 'T' denotes the number of test cases, 'n' denotes the length and width of the matrix, and matrix[i][j] denotes the values at the ith row and jth column.

Time Limit: 1 sec
Sample Input 1 :
2
4 2 2
1 0 0 0
0 0 0 0
0 0 5 1
1 1 1 1
3 2 2
1 1 1
1 0 1
0 0 5
Sample Output1 :
false
true

Explanantion :

For First TestCase there is no path from (0,0) to (2,2).

For Second TestCase one of the path is :-
From (0,0) move right -> (0,1)
From (0,1) move right ->(0,2)
From (0,2) move down ->(1,2)
From (1,2) move dowm ->(2,2).
Sample Input 2 :
2
4 0 1
1 5 1 1 
1 0 1 1 
0 1 1 1 
1 0 1 0 
4 0 3
1 0 0 5 
1 0 0 1 
1 1 1 1 
0 0 1 0
Sample Output 2 :
true
false
Hint

Use Breadth First Search traversal.

Approaches (1)
Approach1

The main idea is to use Breadth First Search traversal from (0,0) coordinate.If we reach the given coordinate return true. Else return false.

Algorithm:

  • Start bfs traversal from the (0,0) coordinate by adding (0,0) in queue pq.
  • If the front coordinates are equal to the given coordinate then return true.
  • Traverse the right and down direction of the front coordinate.
  • If any coordinate in the right direction or down direction is either outside the matrix or is it equal to 0 or is it already visited then do not add it in the queue ‘pq’.Else add it in the queue ‘pq’.
  • After Breadth-First Search return false since the given coordinate was not reachable from (0,0).
Time Complexity

O(N ^ 2) where N is the dimension of the matrix.

 

In the worse case, we need to traverse all coordinates which are N ^ 2 whereas ‘N’ is the length and width of the matrix.

Space Complexity

O(N ^ 2) where N is the dimension of the matrix.

 

In worse space complexity of Breadth First Search is O(V) whereas ‘V’ is the number of vertices that is equal to N ^ 2 whereas ‘N' is the length and width of the matrix.

Code Solution
(100% EXP penalty)
isPath
Full screen
Console