迷宫问题
代码实现
public class MiGong {
public static void main(String[] args) {
//先创建一个二维数组，模拟迷宫
//地图
int[][] map = new int[8][7];
//使用1表示墙
//上下全部置为1
for(int i=0;i<7;i++){
map[0][i]=1;
map[7][i]=1;
}
//左右全部置为1
for(int i=0;i<8;i++){
map[i][0]=1;
map[i][6]=1;
}
//设置挡板 1表示
map[3][1]=1;
map[3][2]=1;
/*map[1][2]=1;
map[2][2]=1;*/
//输出地图
System.out.println("地图情况");
for(int i=0;i<8;i++){
for(int j=0;j<7;j++){
System.out.print(map[i][j]+" ");
}
System.out.println();
}
//使用递归回溯 给小球找路
//setWay(map,1,1);
setWay2(map,1,1);
System.out.println("小球走过，并标识过的地图的情况");
for(int i=0;i<8;i++){
for(int j=0;j<7;j++){
System.out.print(map[i][j]+" ");
}
System.out.println();
}
}
//使用递归回溯来给小球找路
//说明
//1.map表示地图
//2.i,j表示从地图的哪个位置开始出发(1,1)
//3.如果小球能到map[6][5]位置，则说明通路找到
//4.约定：当map[i][j]为0表示该点没有走过 当为1表示墙; 2 表示通路可以走; 3表示该点已经走过，但是走不通
//5.在走迷宫时,需要确定一个策略（方法）下->右->上->左，如果该点走不通，再回溯
/**
* @param map 表示地图
* @param i 从哪个位置开始找
* @param j
* @return 如果找到通路，就返回true,否则返回false
* */
public static boolean setWay(int[][] map,int i,int j){
if(map[6][5] == 2){//通路已经找到ok
return true;
}else{
if(map[i][j]==0){//如果当前这个点还没有走过
//按照策略 下->右->上->左 走
map[i][j]=2;//假定该点可以走通
if(setWay(map,i+1,j)){//向下走
return true;
}else if(setWay(map,i,j+1)){//向右走
return true;
}else if(setWay(map,i-1,j)){//向上
return true;
}else if(setWay(map,i,j-1)){
return true;
}else{
//说明该点是走不通，是死路
map[i][j]=3;
return false;
}
}else{ //如果 map[i][j]!=0,可能是 1,2,3
return false;
}
}
}
//修改找路的策略，改成上->右->下->左
public static boolean setWay2(int[][] map,int i,int j){
if(map[6][5] == 2){//通路已经找到ok
return true;
}else{
if(map[i][j]==0){//如果当前这个点还没有走过
//按照策略 上->右->下->左
map[i][j]=2;//假定该点可以走通
if(setWay2(map,i-1,j)){//向上
return true;
}else if(setWay2(map,i,j+1)){//向右走
return true;
}else if(setWay2(map,i+1,j)){//向下
return true;
}else if(setWay2(map,i,j-1)){//向左走
return true;
}else{
//说明该点是走不通，是死路
map[i][j]=3;
return false;
}
}else{ //如果 map[i][j]!=0,可能是 1,2,3
return false;
}
}
}
}
运行结果
地图情况
1 1 1 1 1 1 1
1 0 0 0 0 0 1
1 0 0 0 0 0 1
1 1 1 0 0 0 1
1 0 0 0 0 0 1
1 0 0 0 0 0 1
1 0 0 0 0 0 1
1 1 1 1 1 1 1
小球走过，并标识过的地图的情况
1 1 1 1 1 1 1
1 2 2 2 2 2 1
1 0 0 0 0 2 1
1 1 1 0 0 2 1
1 0 0 0 0 2 1
1 0 0 0 0 2 1
1 0 0 0 0 2 1
1 1 1 1 1 1 1
对迷宫问题的讨论
1)小球得到的路径，和程序员设置的找路策略有关即：找路的 上下左右 的顺序相关 > > 2)再得到小球路径时，可以先使用(下右上左)，再改成(上右下左)，看看路径是不是有变化 > > 3)测试回溯现象 > > 4) 思考 : 如何求出最短路径 ?
Java 面试宝典是大明哥全力打造的 Java 精品面试题，它是一份靠谱、强大、详细、经典的 Java 后端面试宝典。它不仅仅只是一道道面试题，而是一套完整的 Java 知识体系，一套你 Java 知识点的扫盲贴。
它的内容包括：
- 大厂真题：Java 面试宝典里面的题目都是最近几年的高频的大厂面试真题。
- 原创内容：Java 面试宝典内容全部都是大明哥原创，内容全面且通俗易懂，回答部分可以直接作为面试回答内容。
- 持续更新：一次购买，永久有效。大明哥会持续更新 3+ 年，累计更新 1000+，宝典会不断迭代更新，保证最新、最全面。
- 覆盖全面：本宝典累计更新 1000+，从 Java 入门到 Java 架构的高频面试题，实现 360° 全覆盖。
- 不止面试：内容包含面试题解析、内容详解、知识扩展，它不仅仅只是一份面试题，更是一套完整的 Java 知识体系。
- 宝典详情：https://www.yuque.com/chenssy/sike-java/xvlo920axlp7sf4k
- 宝典总览：https://www.yuque.com/chenssy/sike-java/yogsehzntzgp4ly1
- 宝典进展：https://www.yuque.com/chenssy/sike-java/en9ned7loo47z5aw
目前 Java 面试宝典累计更新 400+ 道，总字数 42w+。大明哥还在持续更新中，下图是大明哥在 2024-12 月份的更新情况：
想了解详情的小伙伴，扫描下面二维码加大明哥微信【daming091】咨询
同时，大明哥也整理一套目前市面最常见的热点面试题。微信搜[大明哥聊 Java]或扫描下方二维码关注大明哥的原创公众号[大明哥聊 Java] ，回复【面试题】 即可免费领取。
