CODEWITHSUNDEEP
javamultidimensional-array
rosie_hyde
rosie_hyde

Reputation: 133

Finding a neighbour in a 2d array

I'm creating a depth first search program which searches through a 2d array to find the number 1 and always starts at 0. I'm having some trouble with finding the neighbours of each element in the array, I have a method (based off the pseudocode found here 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);
          }
        }
      }
    }    


}

Essentially I am trying to go through the 2d array, find each neighbour then place the neighbours into a stack so I can pop them off the stack in the dfs. I've put the maze I am using below along with my output I am currently getting. I would greatly appreciate it if anyone could point me in the right direction/point out anything that seems to be causing it not to find the neighbours.

maze:

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

output:

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

Upvotes: 0

Views: 2907

Answers (1)

Joop Eggen
Joop Eggen

Reputation: 109613

The logic is fine. You could use int instead the Integer Object wrapper. Also using some data structures would be nicer. Rows/y are conventionally vertical maze[y] and columns are horizontally maze[y][x] so maze[y] is a horizontal line.

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

Techniques that exist are:

  • Use walls around the maze, so that considered points start at (1, 1) and you need no boundary checks.
  • Use an array of 8 deltas: `{ (-1, -1), ... , (1, 1) }.

Upvotes: 3

Related Questions