写在前面

本章讲解一个迷宫问题，用来了解方法递归，迷宫和问题如下
问题：求小球从开始到结束的路径，小球从坐标(1,1)开始找，到坐标(5,6)时结束

地图分析实现

1、先得到地图：把地图看做一个二维数组、即 8 行 7 列
2、第一列、最后一列，第一行最后一行，第四行中:第二列，第三列均为障碍物 0 表示可以走 1 表示障碍物，
3.使用 for 循环实现

public class MiGong {

	public static void main(String[] args) {

		// 定义二维数组
		int 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 < 7; i++) {
			map[i][0] = 1;
			map[i][6] = 1;
		}
		// 第四行中:第二列，第三列
		map[3][1] = 1;
		map[3][2] = 1;
		// 输出地图
		System.out.println("===迷宫地图===");
		for (int i = 0; i < map.length; i++) {
			for (int j = 0; j < map[i].length; j++) {
				System.out.print(map[i][j] + " ");
			}
			System.out.println();
		}
	}
}

方法实现

分析

定义找路方法
1、findWay发法用来找出迷宫的路径
2、如果找到就返回true 否则返回 false
3、map 就是二维数组，及表示迷宫
4、i、j 就是老鼠的位置，初始化位置为(1,1)
5、因为是使用递归的找路，所以先规定各个值的含义
---- 1 障碍物 2 表示可以走 3 表示走过走不通 6、当 map[6][5] == 2 就说明找通，可以结束，否则继续找
7、先确定策略 下 -> 右 -> 上 -> 左

public class MiGong {

	public static void main(String[] args) {

		// 定义二维数组
		int 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 < 7; i++) {
			map[i][0] = 1;
			map[i][6] = 1;
		}
		// 第四行中:第二列，第三列
		map[3][1] = 1;
		map[3][2] = 1;
		// 输出地图
		System.out.println("===迷宫地图===");
		for (int i = 0; i < map.length; i++) {
			for (int j = 0; j < map[i].length; j++) {
				System.out.print(map[i][j] + " ");
			}
			System.out.println();
		}

		// 创建对象、调用方法
		A a1 = new A();
		a1.findWay(map,1,1);


		System.out.println("===找路情况===");
		for (int i = 0; i < map.length; i++) {
			for (int j = 0; j < map[i].length; j++) {
				System.out.print(map[i][j] + " ");
			}
			System.out.println();
		}
	}
}

class A {
	public boolean findWay(int map[][],int i, int j) { // 
		if (map[6][5] == 2) {
			return true;
		} else {
			if (map[i][j] == 0) { // 当前这个位置为0，说明可以走
				// 假定可以走通
				map[i][j] = 2;
				// 使用找路策略
				// 下 -> 右 -> 上 -> 左
				if (findWay(map, i + 1, j)) { // 下
					return true;
				} else if(findWay(map,i, j + 1)) { // 右
					return true;
				} else if(findWay(map,i - 1, j)) { // 上
					return true;
				} else if(findWay(map,i, j - 1)){ // 左
					return true;
				} else {
					map[i][j] = 3;
					return false;
				}
			} else {
				return false;
			}

		}
	}
}

结果