Last Updated: 1 Apr, 2021

isPath

Moderate

Asked in company

Solve now

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

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

Solve now

Approaches

01 Approach

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

Solve now