java - 用 Java 解决 2D 迷宫问题

Question

我一直在尝试编写一个程序来解决二维整数迷宫。我不断收到 stackOverFlowError 错误。我结合了案例来设置移动偏好，即北、南、东、西。我在我的递归方法中找不到问题。

import java.util.*;
import java.awt.*;
public class Runner
{
private static int[][] maze =   MazeReader.getMaze("C:\\Users\\owner\\Desktop\\myMaze.txt");
private static int[][] solution = new int[maze.length][maze[0].length];
private static Point[] prefs = new Point[4];
private static int goalX, goalY, startX, startY;
/*
 * if (x,y outside maze) return false
if (x,y is goal) return true
if (x,y not open) return false
mark x,y as part of solution path
if (FIND-PATH(North of x,y) == true) return true
if (FIND-PATH(East of x,y) == true) return true
if (FIND-PATH(South of x,y) == true) return true
if (FIND-PATH(West of x,y) == true) return true
unmark x,y as part of solution path
return false
 */
private static boolean FIND_PATH(int x, int y)
{
    if(x<0||x>=maze.length||y<0||y>=maze[0].length){return false;}
    if(x==goalX&&y==goalY){return true;}
    if(maze[x][y]==1){return false;}
    solution[x][y] = 2;
    if(FIND_PATH(x+(int)prefs[0].getX(),y+(int)prefs[0].getY())){return true;}
    else if(FIND_PATH(x+(int)prefs[1].getX(),y+(int)prefs[1].getY())){return true;}
    else if(FIND_PATH(x+(int)prefs[2].getX(),y+(int)prefs[2].getY())){return true;}
    else if(FIND_PATH(x+(int)prefs[3].getX(),y+(int)prefs[3].getY())){return true;}
    else {solution[x][y] = 0;}
    return false;
}
/*
 * Locate the start position (call it startx, starty).
Call FIND-PATH(startx, starty).
 */
private static void solve(int sx, int sy, int gx, int gy, char p1, char p2, char p3, char p4)
{
    establishPrefs(p1,p2,p3,p4);
    startX = sx;
    startY = sy;
    goalX = gx;
    goalY = gy;
    if(FIND_PATH(startX,startY))
    {
        solution[startX][startY] = 3;
        solution[goalX][goalY] = 4;
    }
    else{System.out.println("No Solution Found");}
    FIND_PATH(startX,startY);
}
private static void establishPrefs(char p1, char p2, char p3, char p4)
{
    switch(p1)
    {
        case 'N': prefs[0] = new Point(0,1);break;
        case 'S': prefs[0] = new Point(0,-1);break;
        case 'E': prefs[0] = new Point(1,0);break;
        case 'W': prefs[0] = new Point(-1,0);break;
    }
    switch(p2)
    {
        case 'N': prefs[1] = new Point(0,1);break;
        case 'S': prefs[1] = new Point(0,-1);break;
        case 'E': prefs[1] = new Point(1,0);break;
        case 'W': prefs[1] = new Point(-1,0);break;
    }
    switch(p3)
    {
        case 'N': prefs[2] = new Point(0,1);break;
        case 'S': prefs[2] = new Point(0,-1);break;
        case 'E': prefs[2] = new Point(1,0);break;
        case 'W': prefs[2] = new Point(-1,0);break;
    }
    switch(p4)
    {
        case 'N': prefs[3] = new Point(0,1);break;
        case 'S': prefs[3] = new Point(0,-1);break;
        case 'E': prefs[3] = new Point(1,0);break;
        case 'W': prefs[3] = new Point(-1,0);break;
    }
}
private static Point[] getPrefs(){return prefs;}
public static void main(String[] args)
{
    MazeReader.display(maze);
    solve(0,0,0,2,'S','E','N','W');
    MazeReader.display(solution);
}

}

Answer 1

尽管您将 solution[x][y] 标记为解决方案路径的一部分，但您并未检查是否返回到解决方案的上一个点。从本质上讲，你最终会陷入原地踏步。

您不得遵循将您引向当前暂定解决方案一部分的位置的路径。

if(maze[x][y]==1){return false;}
if(solution[x][y] == 2) {return false;} // <-- Add
solution[x][y] = 2;