package com.study.recursion;
/** * 迷宫回溯 * @author Administrator * */ public class MiGong {
private static int[][] map = null;
public static void main(String[] args) { init(); showMap(); setWay(map,1,1); showMap(); } /** * 迷宫地图初始化 * @param map */ public static void init() { map = new int[8][7]; for (int i = 0; i < 7; i++) { map[0][i] = 1; map[7][i] = 1; }
for (int i = 0; i < 8; i++) { map[i][0] = 1; map[i][6] = 1; } map[3][1] = 1; map[3][2] = 1; }
/** * 显示迷宫地图 * @param map */ public static void showMap() { for (int i = 0; i < map.length; i++) { for (int j = 0; j < map[0].length; j++) { System.out.printf("%d\t", map[i][j]); } System.out.println(); } System.out.println("============================================================"); } /** * 迷宫寻路方法 * @param map * @param i * @param j * @return */ public static boolean setWay(int[][]map, int i, int j) { if( map[6][5] == 2 ) { 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 { //如果当前节点状态不是0,节点状态是1,2,3 //1.表示墙 //2.表示走过 //3.表示死路 return false; } } }
}
