时间戳

首页 > 解决方案 > 路线规划器二维数组

java - 路线规划器二维数组

问题描述

我正在从这个网站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");
    }
}

标签： javamatrixmultidimensional-array

解决方案

这是我通过所有四个测试的答案：

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)返回，否则返回。true(toRow, toColumn)false

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

推荐阅读