如何在 JAVA 中实现迷宫回溯问题

最编程 2024-06-29 21:19:39

...

public class migong { public static void main(String[] args) { // TODO 自动生成的方法存根 //地图 int [][] map = new int[10][10]; //使用1表示墙 //上下全部置为1 for(int i =0;i<10;i++) { map[0][i] = 1; map[9][i] = 1; } //左右全部置为1 for(int i = 0;i < 10;i++) { map[i][0] = 1; map[i][9] = 1; } //设置挡板 map[3][1] = 1; map[3][2] = 1; map[4][3] = 1; map[5][4] = 1; map[6][5] = 1; map[7][6] = 1; map[8][7] = 1; // 输出地图 for(int i = 0;i < 10;i++) { for(int j = 0;j < 10;j++) { System.out.print(map[i][j]+" "); } System.out.println(); } setWay(map,1,1);//小球起始位置 System.out.println("小球走过，并标识过的地图情况"); for(int i = 0;i < 10;i++) { for(int j = 0;j < 10;j++) { System.out.print(map[i][j]+" "); } System.out.println(); } } //1.使用递归回溯来给小球找路 /*2.map 表示地图 *3. i 从哪个位置开始找(1,1) *4.如果小球找到map[6][5],表示通路已经找到 *约定：当map[i][j]为0表示该点没有走过，当为1表示墙，2表示通路可以走，3表示该点已经走过，但是走不通 *在走迷宫时，需要确定一个策略（方法)，下->右->左->上，如果该点走不通，在回溯 *5. 如果找到通路，就返回true,否则返回false * */ public static boolean setWay(int[][]map,int i ,int j){ if(map[8][8]==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,j-1)) {//向左走 return true; } else if(setWay(map,i-1,j)) {//向上走 return true; }else { map[i][j]= 3;//说明该点走不通，是死路 return false; } }else {//如果map[i][j]！=0,可能是1,2,3 return false; } } } }

上一篇：利用递归回溯法解决迷宫问题

下一篇：迷宫的最短路径