java - 在二维数组中查找邻居

Question

我正在创建一个深度优先搜索程序，它搜索二维数组以查找数字 1，并且始终从 0 开始。我在查找数组中每个元素的邻居时遇到一些麻烦，我有一个方法(基于此处找到的伪代码 Finding neighbours in a two-dimensional array ):

private static void findNeighbour(Integer[][] maze) {

    int row = 0;
    int col = 0;

    int row_limit = maze.length;
    if(row_limit > 0){
     int column_limit = maze[0].length;
     for(int y = Math.max(0, col-1); y <= Math.min(col+1, column_limit); y++){
      for(int x = Math.max(0, row-1); x <= Math.min(row+1, row_limit); x++){
          if(x != row || y != col){
           // printArray(maze);
            neighbours.push(x);
            neighbours.push(y);
          }
        }
      }
    }    


}

本质上，我试图遍历二维数组，找到每个邻居，然后将邻居放入堆栈中，以便我可以将它们从 dfs 中的堆栈中弹出。我将我正在使用的迷宫以及​​我当前获得的输出放在下面。如果有人能指出我正确的方向/指出任何似乎导致它找不到邻居的事情，我将不胜感激。

迷宫:

static Integer[][] maze = { { 11, 3 }, { 2, 3 }, { 0, 3 }, { 1, 4 }, { 5, 4 }, { 5, 7 }, { 6, 7 }, { 7, 8 }, { 8, 9 },
        { 9, 10 }, { 0, 5 } };

输出:

[1, 0, 0, 1, 1, 1]

Answer 1

逻辑没问题。您可以使用 int 代替 Integer 对象包装器。另外使用一些数据结构会更好。行/y 通常是垂直的 maze[y]，列是水平的 maze[y][x]，因此 maze[y] 是水平的线。

private static List<Point> findNeighbours(int[][] maze, Point pt) {
    List<Point> neighbours = new ArrayList<>(8); // Reserve only 8 points
    int height = maze.length;
    if (height > 0) {
        int width = maze[0].length;
        for (int y = Math.max(pt.y - 1, 0); y <= Math.min(pt.y + 1, height); ++y) {
           for (int x = Math.max(pt.x - 1, 0); x <= Math.min(pt.x + 1, width); ++x) {
               if (!(y == pt.y && x == pt.x)) {
                   neighbours.add(new Point(x, y));
               }
           }
        }
    }
    return neighbours;
}

现有的技术有:

• 在迷宫周围使用墙壁，以便考虑的点从 (1, 1) 开始，并且不需要边界检查。
• 使用 8 个增量的数组:`{ (-1, -1), ... , (1, 1) }。