婚庆网站制作公司/网络广告案例

递归：递：传递        归：返回

回溯：从问题的某一状态出发，搜索从这一状态出发所能达到的所有状态，当一条路走到“尽头”时，再后退一步。从另一种可能的状态出发，继续搜索，直到所有的路径都试探过。

这种不断前进，不断后退回溯的方法就叫这个。

思路：使用递归回溯的思想

1.findWay方法为专门来找出迷宫的路径

2.如果找到了，返回true，否则返回false

3.map是二维数组，也就是迷宫

4.i, j是老鼠的位置，初始化是（1，1）

5.因为是递归找数，所以要赋于数组元素各个值的意义

        0表示可以走

        1表示障碍物

        2表示是通路

        3表示走过，但是死路

6.map[6][5] = 2就是找到了一条通路，结束，否则继续找。

7.找路策略：下，右，上，左

// 迷宫问题
public class Maze {public static void main(String[] args) {// 先创建迷宫,元素是0代表可以走，为1是障碍物int[][] map = new int[8][7];// 将迷宫的第一行和最后一行置为1for (int i = 0; i < 7; ++i) {map[0][i] = map[7][i] = 1;}// 将迷宫的第一列和最后一列置为1for (int i = 0; i < 8; ++i) {map[i][0] = map[i][6] = 1;}map[3][1] = map[3][2] = 1;// 极端情况map[1][2] = map[2][1] = map[2][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();}T t1 = new T();t1.findWay(map, 1, 1); // 引用传递，会影响main方法中的数组System.out.println("\n===找路后===");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 T {public boolean findWay(int[][] map, int i, int j) {// 0 可以走// 1 障碍物// 2 是通路// 3 是死路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 { // 1是障碍物走不了，2是通路已经测试过了，3是死路return false;}}}
}

public class HanoiTower {public static void main(String[] args) {Tower tower = new Tower();tower.move(5, 'a', 'b', 'c');}
}class Tower {public void move(int num, char a, char b, char c) {if (num == 1) {System.out.println(a + "->" + c);} else {move(num - 1, a, c, b); // a上面的部分借助c移动到bSystem.out.println(a + "->" + c);move(num - 1, b, a, c);}}
}