Route planner two dimensional array

I'm doing Java tasks from this website https://www.testdome.com/questions/java/route-planner/41102
and got stuck on ArrayIndexOutOfBoundsException error. When you debug code I'll get to finish, but right after that you will get array index is out of bounds. If you open website you will see full task with picture for better understanding. What am I doing wrong?

public static boolean routeExists(int fromRow, int fromColumn, int toRow,
                                  int toColumn, boolean[][] mapMatrix) {
    if (fromRow == mapMatrix.length - 1 && fromColumn == mapMatrix.length - 1) {
        return true;
    }

    goRight(fromRow, fromColumn, mapMatrix);
    goDown(fromRow, fromColumn, mapMatrix);

    return false;
}

private static void goRight(int one, int two, boolean[][] matrix) {
    try {
        if (matrix[one][two + 1]) {
            routeExists(one, two + 1, matrix.length - 1,
                    matrix.length - 1, matrix);
        }
    } catch (ArrayIndexOutOfBoundsException ignore) {
        System.out.println("throw ArrayIndexOutOfBoundsException");
    }
}

private static void goDown(int one, int two, boolean[][] matrix) {
    try {
        if (matrix[one + 1][two]) {
            routeExists(one + 1, two, matrix.length - 1,
                    matrix.length - 1, matrix);
        }
    } catch (ArrayIndexOutOfBoundsException ignore) {
        System.out.println("throw ArrayIndexOutOfBoundsException");
    }
}

Simple solution to pass all 4 test cases:

import java.util.*;
public class RoutePlanner {
public static boolean routeExists(int fromRow, int fromColumn, int toRow, int toColumn,
boolean[][] mapMatrix) {
boolean[][] mapVisited = new boolean[mapMatrix.length][mapMatrix[0].length];
return routeSearch(fromRow, fromColumn, toRow, toColumn,mapMatrix, mapVisited);
}
public static boolean routeSearch(int fromRow, int fromColumn, int toRow, int toColumn,
boolean[][] mapMatrix, boolean[][] mapVisited) {
if(fromRow < 0 || fromColumn < 0 || fromRow >= mapMatrix.length || fromColumn >= mapMatrix[0].length)
return false;
if(mapVisited[fromRow][fromColumn] || !mapMatrix[fromRow][fromColumn]
|| !mapMatrix[toRow][toColumn])
return false;
if(fromRow == toRow && fromColumn == toColumn)
return true;
mapVisited[fromRow][fromColumn] = true;
return routeSearch(fromRow-1, fromColumn, toRow, toColumn, mapMatrix, mapVisited)
|| routeSearch(fromRow, fromColumn-1, toRow, toColumn, mapMatrix, mapVisited)
|| routeSearch(fromRow+1, fromColumn, toRow, toColumn, mapMatrix, mapVisited)            
||routeSearch(fromRow, fromColumn+1, toRow, toColumn, mapMatrix, mapVisited);
}
public static void main(String[] args) {
boolean[][] mapMatrix = {
{true, false, false},
{true, true, false},
{false, true, true}
};
System.out.println(routeExists(0, 0, 2, 2, mapMatrix));        
}
}

Here is my answer which passes all four tests:

import java.util.*;
public class RoutePlanner {
static HashMap<String, ArrayList<String>> graph;
public static boolean routeExists(int fromRow, int fromColumn, int toRow, int toColumn, boolean[][] mapMatrix) {
if(fromRow < 0 || fromColumn < 0 || toRow < 0 || toColumn < 0) {
return false;
}
if(fromRow >= mapMatrix.length || fromColumn >= mapMatrix[0].length || toRow >= mapMatrix.length || toColumn >= mapMatrix[0].length) {
return false; 
}
if(!mapMatrix[fromRow][fromColumn] || !mapMatrix[toRow][toColumn]) {
return false;
}
if(fromRow == toRow && fromColumn == toColumn) {
return true;
}
constructGraph(mapMatrix);
return bfs(fromRow + "-" + fromColumn, toRow + "-" + toColumn);
}
public static void constructGraph(boolean[][] mapMatrix) {
graph = new HashMap<String, ArrayList<String>>();
for(int i = 0; i < mapMatrix.length; i++) {
for(int j = 0; j < mapMatrix[i].length; j++) {
if(!mapMatrix[i][j]) {
continue;
}
String currId = i + "-" + j;
if(i-1 >= 0) {
if(mapMatrix[i-1][j]) {
addEdge(currId, (i-1) + "-" + j);
}
}
if(i+1 < mapMatrix.length) {
if(mapMatrix[i+1][j]) {
addEdge(currId, (i+1) + "-" + j);
}
}
if(j-1 >= 0) {
if(mapMatrix[i][j-1]) {
addEdge(currId, i + "-" + (j-1));
}
}
if(j+1 < mapMatrix[i].length) {
if(mapMatrix[i][j+1]) {
addEdge(currId, i + "-" + (j+1));
}
}
}
}
}
public static void addEdge(String from, String to) {
if(graph.containsKey(from)) {
graph.get(from).add(to);
} else {
ArrayList<String> neighbour = new ArrayList<String>();
neighbour.add(to);
graph.put(from, neighbour);
}
}
public static boolean bfs(String start, String end) {
LinkedList<String> queue = new LinkedList<String>();		// FIFO queue for BFS
HashSet<String> visited = new HashSet<String>();
queue.add(start);
visited.add(start);
String curr;
while(!queue.isEmpty()) {
curr = queue.poll();
if(curr.equals(end)) {
return true;
}
if(!graph.containsKey(curr)) {
return false;
}
for(String next : graph.get(curr)) {
if(!visited.contains(next)) {
visited.add(next);
queue.add(next);
}
}
}
return false;
}
public static void main(String[] args) {
boolean[][] mapMatrix = {
{true,  false, false},
{true,  true,  false},
{false, true,  true}
};
System.out.println(routeExists(0, 0, 2, 2, mapMatrix));
}
}

I am first constructing a graph by connecting two matrix entries if they are adjacent and both are true.

Then, I am doing a simple Breadth-First Search through the graph, starting from the point (fromRow, fromColumn) and returning true once we reach the point (toRow, toColumn), or returning false otherwise.

Note: I am using a String i + "-" + j to give each point in the matrix a unique id.

My recursive solution to this question using visited helper matrix to prevent endless recursion of the same steps over and over:

import java.util.*;
public class RoutePlanner {
public static boolean validMove(boolean[][] mapMatrix,boolean[][] visited, int row, int column) {
if (row >= 0 && column >= 0 && row < mapMatrix.length && column < mapMatrix[row].length ) {
if (mapMatrix[row][column] && !visited[row][column]) // check if move is valid & not visited yet
return true;
}
return false;
}
public static boolean routeExists(int fromRow, int fromColumn, int toRow, int toColumn,
boolean[][] mapMatrix) {
boolean[][] visited = new boolean[mapMatrix.length][mapMatrix[0].length];
return routeExistsHelper(fromRow,fromColumn,toRow,toColumn,mapMatrix,visited);
}
public static boolean routeExistsHelper(int fromRow, int fromColumn, int toRow, int toColumn, boolean[][] mapMatrix, boolean[][] visited) {
visited[fromRow][fromColumn] = true;
if (fromRow == toRow && fromColumn == toColumn)
return true;
else {
boolean left = false, right = false, up = false, down = false;
if (validMove(mapMatrix,visited, fromRow + 1, fromColumn)) {
right = routeExistsHelper(fromRow + 1, fromColumn, toRow, toColumn, mapMatrix,visited);
}
if (validMove(mapMatrix,visited, fromRow - 1, fromColumn)) {
left = routeExistsHelper(fromRow - 1, fromColumn, toRow, toColumn, mapMatrix,visited);
}
if (validMove(mapMatrix,visited, fromRow, fromColumn + 1)) {
up = routeExistsHelper(fromRow, fromColumn + 1, toRow, toColumn, mapMatrix,visited);
}
if (validMove(mapMatrix,visited, fromRow, fromColumn - 1)) {
down = routeExistsHelper(fromRow, fromColumn - 1, toRow, toColumn, mapMatrix,visited);
}
return left || right || up || down;
}
}
public static void main(String[] args) {
boolean[][] mapMatrix = {
{true, false, false},
{true, true, false},
{false, true, true}
};
System.out.println(routeExists(0, 0, 2, 2, mapMatrix));
System.out.println(routeExists(2, 2, 0, 0, mapMatrix));
System.out.println(routeExists(1, 1, 0, 0, mapMatrix));
System.out.println(routeExists(1, 1, 0, 1, mapMatrix));
}
}

routeExists() needs to be a recursive method, i.e. a method that calls itself. When you write a recursive method you first need to write the terminating condition, i.e. if the condition is true then the method does not call itself. If the condition is false then the method should call itself but with different values for the method parameters.

In any method in java, even regular, non-recursive methods, you should always make sure that the method parameters are valid. Hence you need to first check that toRow and toColumn are valid.

You should think of the method parameters fromRow and fromColumn as the indexes of the cell in mapMatrix that you are currently in, and not where you started the matrix traversal from. Of-course, in the first call to method routeExists(), the values of parameters fromRow and fromColumn are the indexes of the start of the route.

There are five terminating conditions for method routeExists().

1. If mapMatrix[toRow][toColumn] is false then a route does not exist, so the method must return false.
2. If fromRow is not a valid index for mapMatrix then the method must return false. Using your example, if fromRow equals 3 then the method must return false.
3. If fromRow is valid, then if fromColumn is not valid then the method must return false.
4. If both fromRow and fromColumn are valid, then if mapMatrix[fromRow][fromColumn] is false, the method must return false.
5. If mapMatrix[toRow][toColumn] is true then if fromRow equals toRow and fromColumn equals toColumn, that means you have reached the destination. In this case the method must return true.

If none of the above terminating conditions are met, then you need to progress to the next cell in mapMatrix and continue checking whether a route exists. In the code below, I arbitrarily decided to progress to the next row. If progressing to the next row does not find a route, I check the next column. Note that the order is not important. You can first move to the next column and after that move to the next row.

Here is the code.

public class RoutePlanner {
    public static boolean routeExists(int fromRow,
                                      int fromColumn,
                                      int toRow,
                                      int toColumn,
                                      boolean[][] mapMatrix) {
        if (mapMatrix == null) {
            return false;
        }

        // Check method parameters for destination.
        if (toRow >= mapMatrix.length) {
            return false;
        }
        if (toColumn >= mapMatrix[toRow].length) {
            return false;
        }

        // Check that destination is reachable.
        if (!mapMatrix[toRow][toColumn]) {
            return false;
        }

        // Check remaining method parameters.
        if (fromRow >= mapMatrix.length) {
            return false;
        }
        if (fromColumn >= mapMatrix[fromRow].length) {
            return false;
        }

        if (!mapMatrix[fromRow][fromColumn]) {
            return false;
        }
        if (fromRow == toRow  &&  fromColumn == toColumn) {
            return true;
        }
        boolean exists = routeExists(fromRow + 1, fromColumn, toRow, toColumn, mapMatrix);
        if (!exists) {
            exists = routeExists(fromRow, fromColumn + 1, toRow, toColumn, mapMatrix);
        }
        return exists;
    }

    public static void main(String[] args) {
        boolean[][] mapMatrix = {{true, false, false},
                                 {true, true, false},
                                 {false, true, true}};

        System.out.println(routeExists(0, 0, 2, 2, mapMatrix));
    }
}