首页 文章

用Java解决2D迷宫

提问于
浏览
0

我一直在尝试制作一个解决2D整数迷宫的程序 . 我一直得到 stackOverFlowError . 我将案件纳入 preferences in movement ,即北,南,东,西 . 我在 recursive method 找不到问题 .

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);
}

}

1 回答

  • 1

    虽然您将 solution[x][y] 标记为解决方案路径的一部分,但您不会检查是否要返回解决方案的前一点 . 从本质上讲,你最终会进入圈子 .

    您不得遵循引导您进入当前暂定解决方案的位置的路径 .

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

相关问题