我们假设数字1表示墙,数字0表示可以走,那么就可以用一个二维数组来模拟一个迷宫,并可以用递归调用来求解路线。
下面的代码是用Java模拟的一个迷宫,代码很简单。
public class MiGong {
public static void main(String[] args) {
int migong[][] = new int[8][7];//定义一个8*7的迷宫
for(int i = 0;i < 7;i++){
migong[0][i] = 1;
migong[7][i] = 1;
}
for(int i = 0;i < 8;i++){
migong[i][0] = 1;
migong[i][6] = 1;
}
migong[3][1] = 1;
migong[3][2] = 1;
for(int i = 0;i < 8;i++){
for(int j = 0;j < 7;j++){
System.out.print(migong[i][j] + " ");
}
System.out.println();
}
}
}
运行后控制台输出如下,其中1代表墙,0表示可以走
1 1 1 1 1 1 1
1 0 0 0 0 0 1
1 0 0 0 0 0 1
1 1 1 0 0 0 1
1 0 0 0 0 0 1
1 0 0 0 0 0 1
1 0 0 0 0 0 1
1 1 1 1 1 1 1
思路分析:
1.我们假设迷宫开始走的起点是migong[1][1],终点是migong[6][5]。
2.首先我们需要先定义一个策略,比如先往下走,如果往下走不通,就往右走,往右再走不通再往左走,最后再走不通就往上走。如果都走不通我们就可以认为这是一条死路。
3.我们约定:1表示墙,0表示没有走过,2表示走过,3表示走不通。
代码实现如下:
public static boolean setPath(int migong[][],int i,int j){
if(migong[6][5] == 2){
return true;
}else{
if(migong[i][j] == 0){
migong[i][j] = 2;//2表示已经走过
if(setPath(migong,i + 1,j))return true;
else if(setPath(migong,i,j+1))return true;
else if(setPath(migong,i - 1,j))return true;
else if(setPath(migong,i,j - 1))return true;
else{
migong[i][j] = 3;
return false;
}
}
else{
return false;
}
}
}