问题描述
一只小老鼠从起点通过一些障碍到达终点，四周的墙壁不能通行，请设计出迷宫路径，使老鼠成功逃出迷宫。
一、解题思想
1、先用二维数组创建一个迷宫
2、用数字表示数组每个元素的不同状态
0 没有障碍物
1 有障碍物
2 走过可以走
3 走过但走不通
3、将最上面和最下面两行以及最左边最右边两行设置为1表示墙
4、将数组中的障碍物都用1表示，输出地图
5、创建一个方法findway用来找出迷宫的路径
6、如果找到返回true，否则返回false
7、确定老鼠找路的策略，先向哪个方向
二、编写代码
1.创建迷宫
代码如下：
public class MiGong { public static void main(String[] args) { //创建map数组表示一个八行七列的迷宫，第四行第2、3个为障碍物 //0代表可以走，1代表障碍物 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 < 8; i++) { map[i][0] = 1; map[i][6] = 1;//左右两列障碍物 } map[3][1] = 1; map[3][2] = 1;//第四行的两个障碍物 //输出迷宫 for (int i = 0; i < 8; i++) { for (int j = 0; j < 7; j++) { System.out.print(map[i][j]);//输出一行 } System.out.println();//输出一行后换行 } } }
会得到一个如下的数组表示迷宫
2.写出findway方法
代码如下：
class F{ //使用递归回溯思想写findway方法 //i,j表示老鼠的位置，最初位置为(1,1) //当map[6][5]=2说明找到通路可以结束，否则继续找 //确定找路策略 下 -> 右 -> 上 -> 左 public boolean findway(int[][] map , int i , int j){//找到返回true，没找到返回false 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{//map[i][j]=1,2,3 return false; } } } }
3.整体代码测试如下
public class MiGong { public static void main(String[] args) { //创建map数组表示一个八行七列的迷宫，第四行第2、3个为障碍物 //0代表可以走，1代表障碍物 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 < 8; i++) { map[i][0] = 1; map[i][6] = 1;//左右两列障碍物 } map[3][1] = 1; map[3][2] = 1;//第四行的两个障碍物 //输出迷宫 for (int i = 0; i < 8; i++) { for (int j = 0; j < 7; j++) { System.out.print(map[i][j]);//输出一行 } System.out.println();//输出一行后换行 } //使用findway方法给老鼠找路 F f1 = new F(); f1.findway(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(); } } } class F{ //使用递归回溯思想写findway方法 //i,j表示老鼠的位置，最初位置为(1,1) //当map[6][5]=2说明找到通路可以结束，否则继续找 //确定找路策略 下 -> 右 -> 上 -> 左 public boolean findway(int[][] map , int i , int j){//找到返回true，没找到返回false 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{//map[i][j]=1,2,3 return false; } } } }
测试结果
数字2所经过的地方就是小老鼠出迷宫的路径
三、总结
找路的策略不同，最后得到的路径就会不同
