Ninja and the Maze
Ninja went to an amusement park and visited a maze. Now, he is stuck in the maze. He can go in any direction(Up, Down, Left, or Right) from this point, but he cannot change his direction of motion until he comes across a wall in its path. Once he stops, he can choose his new direction.

Now, you are given Ninja’s starting point, the destination he wants to reach, and the maze in the form of a 2D matrix. You need to find out if Ninja can reach the destination from the starting point or not.

The maze is represented by a 2D array. ‘1’ means Ninja came across a wall and he needs to stop. ‘0’ means that it is an empty space and he can keep moving.

The coordinates of starting point and destination are represented by row and column numbers.

For Example

Given maze: {[0, 0, 1], [1, 0, 0], [1, 0, 0]} Starting point: [2, 2] Destination: [0, 0] For the above example maze will look like this:

So, we can see there are 2 ways for Ninja to reach destination(D), from the starting point(SP). They are: [left - up - left] and [up - left - up - left]. So, you need to print true.

Input Format:

The first line contains an integer ‘T’ which denotes the number of test cases. The first line of each test case contains two space-separated integers ‘M’ and ‘N’ denoting the dimensions of the maze. The next ‘M’ lines contain ‘N’ space-separated integers each denoting the maze. The next line of each test case contains two space-separated integers ‘startX’ and ‘startY’ denoting the coordinates of the starting point. The last line of each test case contains two space-separated integers ‘destX’ and ‘destY’ denoting the coordinates of the destination.

Output Format

For each test case, print a single line containing a single string containing ‘True’ if it is possible to reach the destination from the starting point and ‘False’ if it is not possible. The output of each test case will be printed in a separate line.

Note:

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints

1

Question

Ninja and the Maze

Ninja went to an amusement park and visited a maze. Now, he is stuck in the maze. He can go in any direction(Up, Down, Left, or Right) from this point, but he cannot change his direction of motion until he comes across a wall in its path. Once he stops, he can choose his new direction.

Now, you are given Ninja’s starting point, the destination he wants to reach, and the maze in the form of a 2D matrix. You need to find out if Ninja can reach the destination from the starting point or not.

The maze is represented by a 2D array. ‘1’ means Ninja came across a wall and he needs to stop. ‘0’ means that it is an empty space and he can keep moving.

The coordinates of starting point and destination are represented by row and column numbers.

For Example

Given maze: {[0, 0, 1], [1, 0, 0], [1, 0, 0]} 
Starting point: [2, 2]
Destination: [0, 0]

For the above example maze will look like this:

So, we can see there are 2 ways for Ninja to reach destination(D), from the starting point(SP). They are: [left -> up -> left] and [up -> left -> up -> left].
So, you need to print true.

Input Format:

The first line contains an integer ‘T’ which denotes the number of test cases.

The first line of each test case contains two space-separated integers ‘M’ and ‘N’ denoting the dimensions of the maze.

The next ‘M’ lines contain ‘N’ space-separated integers each denoting the maze.

The next line of each test case contains two space-separated integers ‘startX’ and ‘startY’ denoting the coordinates of the starting point.

The last line of each test case contains two space-separated integers ‘destX’ and ‘destY’ denoting the coordinates of the destination.

Output Format

For each test case, print a single line containing a single string containing ‘True’ if it is possible to reach the destination from the starting point and ‘False’ if it is not possible.

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

Note:

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints

1 <=T <= 50
1 <= M,N <= 100
0 <= MAZE[ i ] [ j ] <= 1

Where MAZE[ i ][ j ] is the value of the maze. The starting point and destination will always lie in the maze and will be in empty spaces. 

Time limit: 1 sec.

Accepted Answer

Depth First Search

Ninja can move in at most four directions i.e left, right, up, and down.
We will take a 2-D array ‘directions’ of size 4 x 2 in which the first column denotes the shift in the horizontal direction and the second column denotes a shift in the vertical direction.

We will store all the four directions { (0,1) (0,-1) ( 1,0) ( -1,0 ) )} in 2-d array.

In each direction, Ninja continues to move until it will not reach the wall. For example - if Ninja is moving in the left direction, then he will continuously move in the left direction and will stop when reach the wall.
Now we will check the stopping point in each direction. We will add the shift in horizontal and vertical direction until reach the wall. For example, if Ninja is moving in the right direction, we will continuously add (0,1) to the current coordinates of Ninja’s position.
From the stopping point, he can again move in all four directions. So we will recursively solve for all directions from this new point.
If any of the stopping points became equal to our destination, then we can say that we can reach the destination.

There will be many cases in which we will stop at a cell that is already explored. In order to not explore that cell again, we will maintain an extra array ‘visited’.

Algorithm

If coordinates of start = coordinates of destination then return true.
If the current cell is already visited i.e visited[startX][startY] = true, return false.
Otherwise mark current cell as visited.
Initialize a 2-D matrix ‘directions’ with values [ [ 0 1 ] , [ 0 -1 ] [ 1 0 ] [ -1 0 ] ].
Let startX and startY be the x and y coordinates of starting position and destX and destY be the coordinates of the destination.
Let shiftX and shiftY be variables that store shift in x and y-direction.
Run a loop i: 0 to 3 for all the four directions
- Let currentX and currentY be two variables and store startX and startY to it.
- shiftX = directions [ i ][ 0 ] and shiftY = directions[ i ][ 1 ].
- Run a loop while currentX + shiftX is between 0 and length of the maze and currentY + shiftY is between 0 and length of the maze and also maze [ currentX ] [ currentY ] is not equal to ‘1’.
  - Add shiftX to currentX.
  - Add shiftY to currentY.
- Decrement currentX and currentY by shiftX and shiftY.
- Now if visited[ currentX] [ currentY] is equal to false, then it means this cell is not explored yet, so we need to explore the current cell. Therefore, Recursively explore all the directions of currentX and currentY.
Return false if no path found.

Space Complexity: O(m*n) - For 2d arraysExplanation:

O(M * N), where ‘M’ and ‘N’ are the dimensions of the maze.

As we are recursively solving the problem at every stopping point. The maximum number of stopping points will be equal to the size of the maze i.e. M * N. Therefore space complexity would be O(M * N).

Time Complexity: O(m*n) - For 2d arraysExplanation:

O(M * N), where ‘M’ and ‘N’ are the dimensions of the maze.

Every cell of the maze will be visited only once. So the time complexity will be O(M * N).

C++ (g++ 5.4)

/*

	Time Complexity : O(M * N)

	Space Complexity : O(M * N)

	

	where M and N are the dimensions of the maze.

*/



bool reachDestinationHelper(vector> &maze, int m, int n, int startX, int startY, int destX, int destY, vector visited[])

{



    // Return true if coordinates of start and destination are same.

    if (startX == destX && startY == destY)

        return true;



    // Return false if current cell is already visited.

    if (visited[startX][startY] == true)

        return false;



    // Initializing 1-D array to store directions.

    int directions[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};



    // Mark current cell as visited.

    visited[startX][startY] = true;



    // Iterate for every direction.

    for (int i = 0; i < 4; i++)

    {

        // Variables to store starting position.

        int currentX = startX;

        int currentY = startY;



        // Variables to store shift in horizontal or vertical direction.

        int shiftX = directions[i][0];

        int shiftY = directions[i][1];



        // Increment the shift values until wall is not reached or cell value is not '1'

        while (currentX >= 0 && currentX < m && currentY >= 0 && currentY < n && maze[currentX][currentY] == 0)

        {

            currentX = currentX + shiftX;

            currentY = currentY + shiftY;

        }



        // Decrement current position by shift values.

        currentX = currentX - shiftX;

        currentY = currentY - shiftY;



        // Recursively check for current cell it value at current cell is not '0'.

        if (!visited[currentX][currentY] && reachDestinationHelper(maze, m, n, currentX, currentY, destX, destY, visited))

            return true;

    }

    

    // Return false if no path is found to reach destination.

    return false;

}



bool reachDestination(vector> &maze, int m, int n, int startX, int startY, int destX, int destY)

{

    // Initializing 'visited' array.

    vector visited[m];

    for (int i = 0; i < m; i++)

    {

        vector v(n);

        visited[i] = v;

    }



    // Recursive function to check if there is path or not.

    return reachDestinationHelper(maze, m, n, startX, startY, destX, destY, visited);

}

Java (SE 1.8)

/*

	Time Complexity : O(M * N)

	Space Complexity : O(M * N)

	

	where M and N are the dimensions of the maze.

*/



public class Solution {

    public static boolean reachDestinationHelper(int maze[][], int m, int n, int startX, int startY, int destX, int destY, boolean visited[][]) {



        // Return true if coordinates of start and destination are same.

        if (startX == destX && startY == destY) {

            return true;

        }



        // Return false if current cell is already visited.

        if (visited[startX][startY] == true) {

            return false;

        }



        // Initializing 1-D array to store directions.

        int directionsx[] = {0 , 0, 1, -1};

        int directionsy[] = {1 , -1, 0, 0};



        // Mark current cell as visited.

        visited[startX][startY] = true;



        // Iterate for every direction.

        for (int i = 0; i < 4; i++){

            // Variables to store starting position.

            int currentX = startX;

            int currentY = startY;



            int shiftX = directionsx[i];

            int shiftY = directionsy[i];



            // Increment the shift values until wall is not reached or cell value is not '1'.

            while (currentX >= 0 && currentX < m && currentY >= 0 && currentY < n && maze[currentX][currentY] == 0){

                currentX = currentX + shiftX;

                currentY = currentY + shiftY;

            }



            // Decrement current position by shift values.

            currentX = currentX - shiftX;

            currentY = currentY - shiftY;



            // Recursively check for current cell it value at current cell is not '0'.

            if (visited[currentX][currentY] == false && reachDestinationHelper(maze, m, n, currentX, currentY, destX, destY, visited) == true) {

                return true;

            }

        }



        // Return false if no path is found to reach destination.

        return false;

    }

    

    public static Boolean reachDestination(int[][] maze, int m, int n, int startX, int startY, int destX, int destY) {

        boolean visited[][] = new boolean[m][n];

        

        // Recursive function to check if there is path or not.

    	return reachDestinationHelper(maze, m, n, startX, startY, destX, destY, visited);     

    }

}

Python (3.5)

"""

    Time Complexity : O(M * N)

    Space Complexity : O(M * N)



    where 'M' and 'N' are the dimensions of the maze.

"""



def reachDestinationHelper(maze, m, n, startX, startY, destX, destY, visited):



    # Return True if coordinates of start and destination are same.

    if (startX == destX and startY == destY):

        return True



    # Return False if current cell is already visited.

    if (visited[startX][startY] == True):

        return False



    # Initializing 1-D array to store directions.

    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]



    # Mark current cell as visited.

    visited[startX][startY] = True



    # Iterate for every direction.

    for i in range(4):



        # Variables to store starting position.

        currentX = startX

        currentY = startY



        # Variables to store shift in horizontal or vertical direction.

        shiftX = directions[i][0]

        shiftY = directions[i][1]



        # Increment the shift values until wall is not reached or cell value is not '1'

        while (currentX >= 0 and currentX < m and currentY >= 0 and currentY < n and maze[currentX][currentY] == 0):



            currentX = currentX + shiftX

            currentY = currentY + shiftY



        # Decrement current position by shift values.

        currentX = currentX - shiftX

        currentY = currentY - shiftY



        # Recursively check for current cell it value at current cell is not '0'.

        if (visited[currentX][currentY] == False and reachDestinationHelper(maze, m, n, currentX, currentY, destX, destY, visited)):

            return True



    # Return False if no path is found to reach destination.

    return False





def reachDestination(maze, m, n, startX, startY, destX, destY):



    # Initializing 'visited' array.

    visited = []

    for i in range(m):



        v = [False] * n

        visited.append(v)



    # Recursive function to check if there is path or not.

    return reachDestinationHelper(maze, m, n, startX, startY, destX, destY, visited)