深度优先搜索二维arrays
我正在尝试通过创建一个通过迷宫（2d数组）导航我的食人魔的程序来学习DFS。这类似于每日编程挑战，但我只用1×1食人魔做这件事。
我的迷宫：
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 neighbors = new ArrayList(); 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[px][py] == 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 + "(" + px + "," + py + ")"); visited[neighbors.get(i).x][neighbors.get(i).y] = true; dfs(maze, neighbors.get(i)); } return false; } public static ArrayList getNeighbors(int[][] maze, Point p){ ArrayList neighbors = new ArrayList(); Point left = new Point(); Point right = new Point(); Point down = new Point(); Point up = new Point(); down.x = px - 1; down.y = py; if (valid(maze,down)) neighbors.add(down); up.x = px + 1; up.y = py; if (valid(maze,up)) neighbors.add(up); left.x = px; left.y = py - 1; if (valid(maze,left)) neighbors.add(left); right.x = px; right.y = py + 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[px][py] == false) return true; else return false; } public static boolean inMaze(int[][] maze, Point p){ if (px -1 && py -1){ return true; } else return false; } public static boolean canGo(int[][] maze, Point p){ if (maze[px][py] != 1 && maze[px][py] != 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个可能的行并且失败后停止了。
好的，所以我看到一些问题会阻止你的代码正常工作，所以让我们一次看一个。
首先，你的dfs函数不会遍历’for’循环，因为它会立即返回。 尝试改变
dfs(maze, neighbors.get(i));
至
if(dfs(maze, neighbors.get(i))){ return true; }
这可以解决部分问题，只搜索单个路径。
第二个问题是你的邻居。 当您的dfs完全探索路径时，它应该返回一步并检查所有邻居。 您只有一个顶级邻居变量，因此当您的分支以零邻居终止时，它认为所有早期节点都有零邻居。
删除静态邻居变量
static ArrayList neighbors = new ArrayList ();
并在getNeighbors中放置一个非静态版本
ArrayList neighbors = new ArrayList ();
这几乎完全解决了搜索，但对于你的迷宫，你仍然找不到结束。
你的inMaze函数检查边界不正确。 您正在检查x或y是否小于长度减去1。 您只需使用’小于’来检查边界。
if (px < maze[0].length && px > -1 && py < maze.length && py > -1)