isPath
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

Question

isPath

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

Accepted Answer

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

Space Complexity: O(n^2)Explanation:

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.

Time Complexity: O(n^2)Explanation:

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.

C++ (g++ 5.4)

/*
  Time Complexity:O(N ^ 2)
  Space Complexity:O(N ^ 2)
 */

bool isPath(int n, int x, int y, vector>&matrix)
{
	queue>pq;
	// Adding first vertex.
	pq.push({0, 0});
	vector>visited(n, vector(n, false));
	visited[0][0] = true;

	while (!pq.empty())
	{
		vectortemp = pq.front();
		pq.pop();
		int x1 = temp[0];
		int y1 = temp[1];

		if (x1 == x && y1 == y)
		{
			return true;
		}

		// Traversing down and right direction if it satisfies condition add it in the queue.
		if (x1 + 1 < n && (matrix[x1 + 1][y1] == 1 || matrix[x1 + 1][y1] == 5) && !visited[x1 + 1][y1])
		{
			pq.push({x1 + 1, y1});
			visited[x1 + 1][y1] = true;
		}

		if (y1 + 1 < n && (matrix[x1][y1 + 1] == 1 || matrix[x1][y1 + 1] == 5) && !visited[x1][y1 + 1])
		{
			pq.push({x1, y1 + 1});
			visited[x1][y1 + 1] = true;
		}
	}
	return false;


}

Python (3.5)

"""
  Time Complexity:O(N ^ 2)
  Space Complexity:O(N ^ 2)
"""
from collections import deque
def isPath(n, x, y, matrix):

	pq=deque()
	# Adding first vertex.
	pq.append((0,0))
	
	visited=[[False for i in range(n)] for j in range(n)]
	visited[0][0] = True

	while (pq):
	
		temp=pq[0]
		pq.popleft()
		x1 = temp[0]
		y1 = temp[1]

		if (x1 == x and y1 == y):
		
			return True
		
		# Traversing down and right direction if it satisfies condition add it in the queue.
		if (x1 + 1 < n and (matrix[x1 + 1][y1] == 1 or matrix[x1 + 1][y1] == 5) and visited[x1 + 1][y1] is False):
		
			pq.append((x1+1,y1))
			visited[x1 + 1][y1] = True
		
		if (y1 + 1 < n and (matrix[x1][y1 + 1] == 1 or matrix[x1][y1 + 1] == 5) and visited[x1][y1 + 1] is False):
		
			pq.append((x1,y1+1))
			visited[x1][y1 + 1] = True

	return False

Java (SE 1.8)

/*
	Time Complexity:O(N ^ 2)
	Space Complexity:O(N ^ 2)
 */

import java.util.ArrayList;

public class Solution 
{
    public static boolean isPath(int n, int x, int y,int matrix[][])
    {
		ArrayList> pq = new ArrayList>();
		// Adding first vertex.
		ArrayList aa = new ArrayList();
		aa.add(0);
		aa.add(0);
		pq.add(aa);
		ArrayList> visited = new ArrayList>(n);
		for(int i = 0; i < n; i++)
		{
			ArrayList temp1 = new ArrayList(n);
			for(int j = 0; j < n; j++)
			{
				temp1.add(false);
			}
			visited.add(temp1);
		}
		visited.get(0).set(0,true);
		while (pq.size() != 0)
		{
			int x1 = pq.get(0).get(0);
			int y1 = pq.get(0).get(1);
			pq.remove(0);
			if (x1 == x && y1 == y)
			{
				return true;
			}

			// Traversing down and right direction if it satisfies condition add it in the pq.
			if (x1 + 1 < n && (matrix[x1 + 1][y1] == 1 || matrix[x1 + 1][y1] == 5) && !visited.get(x1 + 1).get(y1))
			{
				ArrayList temp2 = new ArrayList();
				temp2.add(x1 + 1);
				temp2.add(y1);
				pq.add(temp2);
				visited.get(x1 + 1).set(y1,true);
			}

			if (y1 + 1 < n && (matrix[x1][y1 + 1] == 1 || matrix[x1][y1 + 1] == 5) && !visited.get(x1).get(y1 + 1))
			{
				ArrayList temp3 = new ArrayList();
				temp3.add(x1);
				temp3.add(y1 + 1);
				pq.add(temp3);
				visited.get(x1).set(y1 + 1,true);
			
			}
		}
		 return false;
    }

}

For Example :

Input Format :

Output Format :

Constraints :

Top Amazon Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in Amazon Software Developer