0

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]
Community
  • 1
  • 1
rosie_hyde
  • 133
  • 1
  • 4
  • 12
  • It looks right to me. The neighbors of (0, 0) are (1, 0), (0, 1) and (1, 1) and that's what's in `neighbors`. What do you expect it to contain? (By the way, your loops should have `Math.min(col+1, column_limit-1)` and `Math.min(row+1, row_limit-1)` since the length of the array is an illegal index for that array. Or else set `row_limit` to `maze.length-1` and similarly for `column_limit`.) – Ted Hopp Jan 09 '17 at 20:47
  • @TedHopp Ah that makes sense, I thought it was showing the actual element in the array (what I actually want) as opposed to the coordinate. – rosie_hyde Jan 09 '17 at 20:51
  • this is not the true way of implementing it ... why do you not try to implement it using recursive function? are scared of stackoverflow for the recursion stack ? – Mohsen_Fatemi Jan 09 '17 at 20:53
  • @Mohsen_Fatemi, that’s pretty much a matter of taste, either approach works. – Ole V.V. Jan 09 '17 at 20:59
  • @Mohsen_Fatemi No reason other than this looked simpler to implement and that I found pseudocode which helped me understand this implementation. – rosie_hyde Jan 09 '17 at 21:02

1 Answers1

3

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) }.
Joop Eggen
  • 107,315
  • 7
  • 83
  • 138
  • Thank you for explaining this so well that really helps, my only question is about the Point. Is there a way of pushing this onto a stack rather than adding it to an array list? I only ask because of how the data will be used. – rosie_hyde Jan 10 '17 at 11:39
  • 1
    If you use a stack of points, like `Deque stack = new ArrayDeque<>();` (`Deque` is a more modern version than the older `Stack`). As says the javadoc of [Stack itself](https://docs.oracle.com/javase/8/docs/api/java/util/Stack.html) – Joop Eggen Jan 10 '17 at 20:53