解决Java中的2D迷宫

Question

我一直在试图制作一个解决2D整数迷宫的程序。我不断收到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;