Java 递归迷宫

Question

这个问题已经有答案了:

Recursive brute force maze solver Java (1 个回答)

已关闭 8 年前。

我的任务是用 Java 创建一个迷宫求解器。我决定应用的算法按以下方式工作:它是一种递归移动方法，每次找到路径时都会再次调用自身。如果遇到死胡同，它会调用第二个递归方法“goBack”，该方法会不断返回，直到找到新路径。墙壁为 0，路径为 1，走过的路径为 2，走过两次的路径为 3。这个想法很简单，但我就是无法让它发挥作用。 ArrayOutOfBounds 异常一直出现。有人对此有什么想法吗？

public class Project5v2 {

static String mazecsv = "/Users/amorimph/Documents/COMP 182/Project 5/mazeinput.csv";
static File solvedMaze = new File("/Users/amorimph/Documents/COMP 182/Project 5/solvedMaze.txt");
static int[][] maze = new int[50][50];
static int trigger = 0;
static int mazeWidth;
static int mazeHeight;

public static void main(String[] args) {

    readCSV(mazecsv);
    start(maze);
    mazeToString(maze);

}

public static void readCSV(String csvfile) {

    BufferedReader br = null;
    String line = "";
    String csvSplitBy = ",";
    int x = 1;
    int y = 0;


    try {

        br = new BufferedReader(new FileReader(csvfile));
        br.readLine();

           while ((line = br.readLine()) != null) {

               String[] info = line.split(csvSplitBy);

               for (x = 1; x < info.length; x++) {                       
                      maze[y][x] = Integer.parseInt(info[x]);
                }
                mazeWidth = info.length;
               y++;
               mazeHeight = y;

             }

    } catch (FileNotFoundException e) {
        e.printStackTrace();
    } catch (IOException e) {
        e.printStackTrace();
    } finally {
        if (br != null) {
            try {
                br.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
    }

 }

public static void start(int[][] maze) {

int i = 0;
while(maze[0][i] != 1) {
    i++;
}
System.out.println(i);
move(maze,i,1);

}

public static void move(int[][] maze, int x, int y) {


for (int i = 0; i < 4; i++) {
    switch(i) {

    case 0: if(maze[x][y-1] == 1) {
        maze[x][y] = 2;
        maze[x][y-1] = 2;
        move(maze, x, y-1);
        break;
    }

    case 1: if(maze[x-1][y] == 1) {
        maze[x][y] = 2;
        maze[x-1][y] = 2;
        move(maze, x-1, y);
        break;
    }

    case 2: if(maze[x+1][y] == 1) {
        maze[x][y] = 2;
        maze[x+1][y] = 2;
        move(maze, x+1, y);
        break;
    }

    case 3: if(maze[x][y+1] == 1) {
        maze[x][y] = 2;
        maze[x][y+1] = 2;
        move(maze, x, y+1);
        break;
    }

    //case 4:
    //  maze[x][y] = 2;
    //  goBack(maze, y, x);
    //  break;

    }
}
}

public static void goBack(int[][] maze, int x, int y) {

for (int i = 0; i < 7; i++) {
    switch(i) {

    case 0: if(maze[x][y-1] == 1) {
        maze[x][y] = 2;
        maze[x][y-1] = 2;
        move(maze, x, y-1);
        break;
    }

    case 1: if(maze[x-1][y] == 1) {
        maze[x][y] = 2;
        maze[x-1][y] = 2;
        move(maze, x-1, y);
        break;
    }

    case 2: if(maze[x+1][y] == 1) {
        maze[x][y] = 2;
        maze[x+1][y] = 2;
        move(maze, x+1, y);
        break;
    }

    case 3: if(maze[x][y+1] == 1) {
        maze[x][y] = 2;
        maze[x][y+1] = 2;
        move(maze, x, y+1);
        break;
    }

    case 4: if(maze[x][y+1] == 2) {
        maze[x][y] = 3;
        goBack(maze, x, y+1);
        break;
    }

    case 5: if(maze[x+1][y] == 2) {
        maze[x][y] = 3;
        goBack(maze, x+1, y);
        break;
    }

    case 6: if(maze[x-1][y] == 2) {
        maze[x][y] = 3;
        goBack(maze, x-1, y);
        break;
    }

    case 7: if(maze[x][y-1] == 2) {
        maze[x][y] = 3;
        goBack(maze, x, y-1);
        break;
    }
    }
}
}

public static void FWriter(String content, File file) {

try {         
       if (!file.exists()) {
        file.createNewFile();
       }     
       FileWriter fw = new FileWriter(file.getAbsoluteFile(), true);
       BufferedWriter bw = new BufferedWriter(fw);
       bw.write(content);
       bw.close();           
}         
catch (IOException e) {
        e.printStackTrace();
}
}

public static void mazeToString(int[][] maze) {

    for(int i = 0; i < mazeHeight; i++) {
        for(int j = 0; j < mazeWidth; j++) {
            FWriter(Integer.toString(maze[i][j]), solvedMaze);
        }
        FWriter("\n", solvedMaze);
    }
}

}

Answer 1

你的迷宫是50*50。

查看你的移动方法，我看不出有什么可以阻止你掉出迷宫(即移动到大于 49 或小于 0 的索引)。

更一般地说，如果您想使用递归，并且不想陷入麻烦，则必须检查何时完成。您的 move 方法永远不会停止调用自身，因此请考虑 move 方法应在什么时候终止。