我正在尝试通过创建一个程序,使我的食人魔在迷宫(2D数组)中导航来学习DFS。这类似于每日编程挑战,但我只使用了一个1x1的食人魔。
我的迷宫:
static int[][] maze = {
{2,1,0,0,0,0,0,0,0,0},
{0,0,1,0,0,0,0,0,0,0},
{1,0,0,0,0,1,0,1,0,0},
{0,0,0,0,0,0,0,0,0,0},
{0,0,1,1,0,0,0,0,0,0},
{0,0,1,0,0,0,0,1,0,1},
{1,1,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,1,1,0,0,0},
{0,0,0,0,0,1,0,0,0,3}};
在这个程序中,2代表我的英雄(起点)位于坐标 (0,0),3代表终点位于坐标 (9,9),1代表障碍物,0代表可以通过的空间。
由于我是新手,可能不需要这一步骤,但我会包含整个程序以方便复制和故障排除。
import java.awt.Point;
import java.util.ArrayList;
public class OgrePath {
static int[][] maze = {
{2,1,0,0,0,0,0,0,0,0},
{0,0,1,0,0,0,0,0,0,0},
{1,0,0,0,0,1,0,1,0,0},
{0,0,0,0,0,0,0,0,0,0},
{0,0,1,1,0,0,0,0,0,0},
{0,0,1,0,0,0,0,1,0,1},
{1,1,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,1,1,0,0,0},
{0,0,0,0,0,1,0,0,0,3}};
public static boolean[][] visited = new boolean[maze.length][maze[0].length];
static ArrayList<Point> neighbors = new ArrayList<Point>();
public static void main(String[] args) {
OgrePath OP = new OgrePath();
for (int i=0;i<maze.length;i++){
for (int j=0;j<maze[i].length;j++){
visited[j][i] = false;
}
}
visited[getOgre(maze).x][getOgre(maze).y] = true;
System.out.println("Ogre: " + getOgre(maze));
dfs(maze, getOgre(maze));
}
public static boolean dfs(int[][] maze, Point p){
neighbors = getNeighbors(maze,p);
if (maze[p.x][p.y] == 3){
System.out.println("FOUND IT");
return true;
}
if (neighbors.isEmpty()){
return false;
}
for (int i=0;i<neighbors.size();i++){
System.out.println("Nieghbors: " + neighbors);
System.out.println(i + "(" + p.x + "," + p.y + ")");
visited[neighbors.get(i).x][neighbors.get(i).y] = true;
dfs(maze, neighbors.get(i));
}
return false;
}
public static ArrayList<Point> getNeighbors(int[][] maze, Point p){
ArrayList<Point> neighbors = new ArrayList<Point>();
Point left = new Point();
Point right = new Point();
Point down = new Point();
Point up = new Point();
down.x = p.x - 1;
down.y = p.y;
if (valid(maze,down)) neighbors.add(down);
up.x = p.x + 1;
up.y = p.y;
if (valid(maze,up)) neighbors.add(up);
left.x = p.x;
left.y = p.y - 1;
if (valid(maze,left)) neighbors.add(left);
right.x = p.x;
right.y = p.y + 1;
if (valid(maze,right)) neighbors.add(right);
return neighbors;
}
public static boolean valid(int[][] maze, Point p){
if (inMaze(maze,p) && canGo(maze,p) && visited[p.x][p.y] == false) return true;
else return false;
}
public static boolean inMaze(int[][] maze, Point p){
if (p.x < (maze[0].length - 1) && p.x > -1 && p.y < (maze.length - 1) && p.y > -1){
return true;
} else return false;
}
public static boolean canGo(int[][] maze, Point p){
if (maze[p.x][p.y] != 1 && maze[p.x][p.y] != 4) return true;
else return false;
}
public static Point getOgre(int[][] maze){
Point ogre = new Point();
for (int i=0;i<maze.length;i++){
for (int j=0;j<maze[i].length;j++){
if (maze[i][j] == 2){
ogre.x = j;
ogre.y = i;
}
}
}
return ogre;
}
}
我希望能够递归调用DFS,但是我写的代码有问题,程序探索了1条可能的路径并失败后就停止了。