对于走迷宫问题，可能我们经常用的是深度优先搜索，本来我对学习的态度是只要知道一种处理办法就行了，可是我想到在街上找厕所的时候，想一想还是看一下最短路径是怎么弄的吧
接下来先来看一下深度优先搜索
首先对于一个迷宫，1是墙，0是路如下图所示
image.png
那么对于深度优先搜索我先采取递归的方式来求解这个问题
首先来进行几个约定在求解之前，1代表墙，0代表没有走过的路，2代表走过的路，3代表该路不通
这个递归里面应该传入这个地图也就是这个矩阵数组，和当前所处的位置
1).首先判断目的地是否为2，如果为2则表示已有路可达，返回true
2).如果没有则判断当前位置是否为0，如果为0则继续探行
2-1).根据此点往四处寻找，如果某一处返回true，则该分支返回true，否则将此点设置为3并且返回为false
3).如果不是则返回false（可能出现1，2，3）
代码如下
public class Migong {
public static void main(String[] args) {
int[][] map = new int[8][7];
for(int i=0;i<8;i++){
map[i][0] = 1;
map[i][6] = 1;
}
for(int i=0;i<7;i++){
map[0][i] = 1;
map[7][i] = 1;
}
map[3][1] = 1;
map[3][2] = 1;
sout(map);
dept(map,1,1);
System.out.println();
sout(map);
}
public static void sout(int[][] map){
for(int[] row:map){
for(int item:row){
System.out.print(item + " ");
}
System.out.println();
}
}
public static boolean dept(int[][] map,int i, int j){
if(map[6][5]==2){
return true;
}else {
if(map[i][j] == 0){
map[i][j] = 2;
if(dept(map,i+1,j)){
return true;
}else if(dept(map,i,j+1)){
return true;
}else if(dept(map,i-1,j)){
return true;
}else if (dept(map,i,j-1)){
return true;
}else {
map[i][j] = 3;
return false;
}
}else {
return false;
}
}
}
}
运行结果如下
image.png
接下来探讨最短路径，最短路径应该是有由一个点往四处扩展，在某一层如果某一个点探寻到了，则为最短路径（深度最小），因为在这一层以前还没有答案，所以为最短
具体细节我们可以：
1.创建一个类保存走过的路径以及和上一个点的数据
1.创建一个队列，并将起始位置入队
2.将队列里面的取出一个点往四处探寻，为0的入队列
3.判断入队列的点是不是终点，是则停止
4.将2-3反复调用
代码如下，输出路径从下往上看（数据结构和算法的新手，请勿喷）
public class BreadMigong {
private static Queue<Step> queue = new ArrayDeque<>();
public static void main(String[] args) {
int[][] map = new int[8][7];
for(int i=0;i<8;i++){
map[i][0] = 1;
map[i][6] = 1;
}
for(int i=0;i<7;i++){
map[0][i] = 1;
map[7][i] = 1;
}
map[3][1] = 1;
map[3][2] = 1;
queue.add(new Step(1,1,null));
Step res = null;
while (!queue.isEmpty()){
Step step = queue.poll();
res = toNext(step, map,1,0);
if(res != null)
break;
res = toNext(step, map,-1,0);
if(res != null)
break;
res = toNext(step, map,0,1);
if(res != null)
break;
res = toNext(step, map,0,-1);
if(res != null)
break;
}
while (res != null){
System.out.println(res.getRow() + " " + res.getCol());
res = res.getPri();
}
}
public static Step toNext(Step step,int[][] map, int i, int j){
if(map[step.getRow() + i][step.getCol() + j] == 0){
Step temp = new Step(step.getRow() + i, step.getCol() + j, step);
queue.add(temp);
map[step.getRow() + i][step.getCol() + j] = 2;
if(map[6][5] == 2) {
return temp;
}
}
return null;
}
}
class Step{
private int row;
private int col;
private Step pri;
public Step(int row, int col, Step pri) {
this.row = row;
this.col = col;
this.pri = pri;
}
public int getRow() {
return row;
}
public void setRow(int row) {
this.row = row;
}
public int getCol() {
return col;
}
public void setCol(int col) {
this.col = col;
}
public Step getPri() {
return pri;
}
public void setPri(Step pri) {
this.pri = pri;
}
@Override
public String toString() {
return "Step{" +
"row=" + row +
", col=" + col +
'}';
}
}
