路径规划器二维阵列

Question

我正在做这个网站https://www.testdome.com/questions/java/route-planner/41102的Java任务，并且被ArrayIndexOutOfBoundsException错误困住了。当您调试代码时，我将完成，但之后您将得到数组索引超出了范围。如果您打开网站，您将看到完整的任务与图片，以更好地理解。我做错了什么？

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");
    }
}

Answer 1

以下是我的答案，它通过了所有四个测试：

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));
    
}
}

我首先通过连接两个矩阵条目来构造一个图，如果它们是相邻的，并且都是true。

然后，我做一个简单的宽度优先搜索图，从点(fromRow, fromColumn)开始，在到达点(toRow, toColumn)后返回true，否则返回false。

注意:我使用字符串i + "-" + j给矩阵中的每个点一个唯一的id。

Answer 2

通过所有4个测试用例的简单解决方案：

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));        
    }
}

Answer 3

我对这个问题的递归解决方案使用了visited帮助矩阵，以防止重复重复地重复重复地递归相同的步骤：

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));
    }
}