我试图通过创建一个程序来学习 DFS,该程序可以引导我的食人魔穿过迷宫(二维数组)。这类似于日常编程挑战,但我只用一个 1x1 食人魔来完成。
My maze:
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 个可能的行并失败后停止。