本文共 3222 字，大约阅读时间需要 10 分钟。
一看就是BFS的题，但地图太大了，纯BFS的话会超时。题目中正好给了blocked的大小限制，我们就让遍历足够多的节点后停下来就行了。我也比较快的想到这点了，但这题还是把我恶心到了。恶心的地方就是我用红框框出的部分，去你码的，骗人！害老子找了那么久问题，CNM！以后用例能不能认真写一下啊LeetCode。
class Solution { private int max = (int) Math.pow(10, 6); private int maxStep = 200; public boolean isEscapePossible(int[][] blocked, int[] source, int[] target) { // 标记source和target为已访问，避免被阻挡区域处理 for (int i = 0; i < blocked.length; i++) { if ((blocked[i][0] == source[0] && blocked[i][1] == source[1]) || (blocked[i][0] == target[0] && blocked[i][1] == target[1])) { blocked[i][0] = -1; blocked[i][1] = -1; } } Set visited1 = new HashSet<>(); Set visited2 = new HashSet<>(); Queue q1 = new LinkedList<>(); Queue q2 = new LinkedList<>(); if (bfs(q1, visited1, source, target, blocked, maxStep, maxArea)) { return true; } if (bfs(q2, visited2, target, source, blocked, maxStep, maxArea)) { return true; } if (visited1.size() > maxArea || visited2.size() > maxArea) { return true; } return false; } private boolean bfs(Queue queue, Set visited, int[] start, int[] end, int[][] blocked, int maxStep, int maxArea) { int step = 0; queue.add(start); visited.add(intToString(start[0]) + "," + intToString(start[1])); while (!queue.isEmpty()) { int[] current = queue.poll(); step++; if (step > maxStep) { return false; } if (current[0] == end[0] && current[1] == end[1]) { return true; } // 检查四个方向 // 上 if (validMove(blocked, current[0], current[1] - 1, visited, maxArea)) { queue.add(new int[]{current[0], current[1] - 1}); } // 下 if (validMove(blocked, current[0], current[1] + 1, visited, maxArea)) { queue.add(new int[]{current[0], current[1] + 1}); } // 左 if (validMove(blocked, current[0] - 1, current[1], visited, maxArea)) { queue.add(new int[]{current[0] - 1, current[1]}); } // 右 if (validMove(blocked, current[0] + 1, current[1], visited, maxArea)) { queue.add(new int[]{current[0] + 1, current[1]}); } // 检查是否已遍历足够多的节点 if (visited.size() > maxArea) { return false; } } return false; } private boolean validMove(int[][] blocked, int x, int y, Set visited, int maxArea) { // 检查是否越界 if (x < 0 || x >= max || y < 0 || y >= max) { return false; } // 检查是否已访问 if (visited.contains(intToString(x) + "," + intToString(y))) { return false; } // 检查是否被阻挡 for (int[] i : blocked) { if (i[0] == x && i[1] == y) { return false; } } // 添加到已访问集合 visited.add(intToString(x) + "," + intToString(y)); // 限制最大遍历节点数 if (visited.size() > maxArea) { return false; } return true; } private String intToString(int num) { return Integer.toString(num); } // 其他必要的方法} 问题分析：这是一个典型的广度优先搜索（BFS）问题，用于判断是否存在一条从起点到终点的路径，避开被阻挡的区域。由于地图可能非常大，普通的BFS可能会超时，因此需要优化。
优化策略：利用题目中给定的blocked大小限制，设置一个最大遍历步数maxStep和最大遍历节点数maxArea。BFS在超过这些限制时提前终止，避免不必要的计算。
算法实现：
代码结构：主要包含两个集合和两个队列，分别用于两种BFS方向。每个BFS函数处理一方向，检查路径是否存在并提前终止。
效率优化：通过设置合理的maxStep和maxArea，确保算法在有限的时间内完成搜索，适用于大规模地图。
转载地址：http://fuee.baihongyu.com/