package com.bei.Demo01_recursion;
public class MiGong {
public static void main(String[] args)
{
//First create a two-dimensional array to simulate the maze
int [][]map=new int[8][7];
//Use 1 for wall
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;
}
//Set the bezel
map[3][1]=1;
map[3][2]=1;
//Output
for (int i = 0; i <8 ; i++) {
for (int j = 0; j < 7; j++) {
System.out.print(map[i][j]+" ");
}
System.out.println();
}
System.out.println("----------------------------");
setWay(map,1,1);
for (int i = 0; i <8 ; i++) {
for (int j = 0; j < 7; j++) {
System.out.print(map[i][j]+" ");
}
System.out.println();
}
}
//Use recursive backtracking to find the way to the ball
//1.mapRepresents the map
//2.i,j Indicates starting from that location on the map (1,1)
//2.If you can get to the location of map[6][5], then you can go
//4Convention: When map[i][j]=0, it means that it has not been found. 1 means that the wall 2 means that the path can be taken. 3 means that the point has been passed but cannot be passed.
//5.Strategy: Down-Right-Up-Left, if the point cannot be reached, backtrack
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 {
return false;
}
}
}
}
Comments
Post a Comment