当前位置 博文首页 > lenkee的博客：算法小程序：逃离大迷宫
在一个 10^6 x 10^6 的网格中，每个网格块的坐标为 (x, y)，其中 0 <= x, y < 10^6。
我们从源方格 source 开始出发，意图赶往目标方格 target。每次移动，我们都可以走到网格中在四个方向上相邻的方格，只要该方格不在给出的封锁列表 blocked 上。
只有在可以通过一系列的移动到达目标方格时才返回 true。否则，返回 false。
示例 1：
输入：blocked = [[0,1],[1,0]], source = [0,0], target = [0,2]
输出：false
解释：
从源方格无法到达目标方格，因为我们无法在网格中移动。
示例 2：
输入：blocked = [], source = [0,0], target = [999999,999999]
输出：true
解释：
因为没有方格被封锁，所以一定可以到达目标方格。
提示：
0 <= blocked.length <= 200
blocked[i].length == 2
0 <= blocked[i][j] < 10^6
source.length == target.length == 2
0 <= source[i][j], target[i][j] < 10^6
source != target
链接：https://leetcode-cn.com/problems/escape-a-large-maze
刚开始看到这道题的时候，第一个想法就是动态递归的方法，每走一步，把往后的所有步骤列举出来，最后判断可行不可行。但是这种递归方法很容易栈溢出，大概棋盘20x20往后就溢出了，题目给的10^6 x 10^6实在太大，递归方法不可行。
将递归转换成非递归方法。
- 每走一步，标记状态放进栈中，一直到走不通；
- 走不通后开始倒退，将退出的格子从栈中移除，并且标记为不可走;
- 然后继续判断上下左右是否可行，不可行继续往后退，直到找到可行的路，重复第一步。
这样，可以一直执行，且内存消耗也不大。
但是，缺点是比较耗时，因为它一直是试探性的往前走。
提示有一个要求0 <= blocked.length <= 200，所以利用这个条件，则围成个三角形可以围住最多的点,即(200*200)/2-200/2=19900个点(三角形面积+斜边超出部分的面积),从起点S走了超出19900步没有被围住，所以，只需要多加一个判断条件即可
但是，认为是可以抵达终点T是不对的,因为障碍点可能围住了终点T,所以也得需要判断从终点T是否也可到达起点S
下面是用java实现的逃离大迷宫算法
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;
/**
* Created by amettursun on 2019/7/5.
*/
public class 逃离大迷宫 {
/**
* 在一个 10^6 x 10^6 的网格中，每个网格块的坐标为 (x, y)，其中 0 <= x, y < 10^6。
我们从源方格 source 开始出发，意图赶往目标方格 target。每次移动，我们都可以走到网格中在四个方向上相邻的方格，只要该方格不在给出的封锁列表 blocked 上。
只有在可以通过一系列的移动到达目标方格时才返回 true。否则，返回 false。
*/
// 记录行走路径
public static Stack<int[]> trace = new Stack<>();
// 设置棋盘大小6x6
public static int scope = 6;
public static void main(String[] args) {
// 设置棋盘阵型
int[][] blocked = {{3,2},{4,2},{5,3},{4,4},{2,5}};
// 起点
int[] source = new int[]{0,0};
//终点
int[] target = new int[]{5,5};
System.out.println("^ v ^");
// 判断是否走得通
boolean escapePossible = isEscapePossible(blocked, source, target);
System.out.println( escapePossible);
if (escapePossible){
trace.stream().forEach(t->{
System.out.print("{"+t[0]+","+t[1]+"}-->");
});
}
}
public static Map<String, Integer> dealData(int[][]blocked){
Map<String, Integer> graph= new HashMap<>();
for (int i = 0; i < blocked.length; i++) {
int x = blocked[i][0];
int y = blocked[i][1];
String key = x+""+y;
graph.put(key,1);
}
return graph;
}
// 判断是否超出范围
public static boolean outOfScope(int x, int y,Map<String, Integer> graph){
return x>=0 && y>=0 && x<scope && y<scope && getGraph(graph,x+""+y)==0;
}
public static boolean isEscapePossible(int[][] blocked, int[] source, int[] target){
// Stack<int[]> trace = new Stack<>();
Stack<int[]> trace2 = new Stack<>();
// 正向和逆向，都走一遍
return isEscapePossible2(blocked, source, target, trace) && isEscapePossible2(blocked, target, source, trace2);
}
public static boolean isEscapePossible2(int[][] blocked, int[] source, int[] target, Stack<int[]> trace){
Map<String, Integer> graph = dealData(blocked);
// 上下左右轮询，一直到taget和source是同一个点为止
trace.add(source.clone());
while (true){
int x = source[0];
int y = source[1];
// 出口
if (x == target[0] && y==target[1]){
return true;
}
if (trace != null && trace.size() > 19900)
return true;
// 上
if (goAhead(graph,source, 1)){
// 移动成功，将路径加入到stack里面, 移动source
trace.add(source.clone());
continue;
}else if (goAhead(graph,source, 2)){
// 下
trace.add(source.clone());
continue;
}else if (goAhead(graph,source, 3)){
// 左
trace.add(source.clone());
continue;
}else if (goAhead(graph,source, 4)){
// 右
trace.add(source.clone());
continue;
}else {
// 失败，回撤
int[] ints = rollBack(trace, graph);
if (ints != null)
source = ints.clone();
else
source = null;
}
// 退回到起点, 走投无路
if (trace.size() ==0 && source == null){
return false;
}
}
}
// 如果能走，则走到下一步，返回true，否则返回false
public static boolean goAhead(Map<String, Integer> graph,int[]source, int director){
// 1.上 2.下 3.左 4.右
int x = source[0];
int y = source[1];
switch (director){
case 1:{
if (outOfScope(x-1, y,graph)){
blockGraph(graph,source,1)
