Find and validate immediate neighbors of the given source node of a 2D matrix?

user_9933951 0
Viewed 123

I am working on a Javascript project for the pathfinding visualiser where I am having difficulty in finding and validating the immediate neighbours of a source node in a 2D Matrix.

Problem Statement: Given a sorted 4X3 2D matrix, let's say array=[{1,2,3,4},{5,6,7,8},{9,10,11,12}] in which we have to find immediate neighbours (LEFT, RIGHT, UP, DOWN) of a given number. It's easy to calculate the left or right just by adding or subtract 1 and add or subtract 4 for the bottom or up, But for the elements at extreme end.

  • How do we validate that number returned is a neighbour or not?*

Example: neighbour(5) = [ 1,6,9 ] (4 isn't a neighbour)

also neighbour(7) = [ 3,6,8,11]


         left = source -1 ;
         right = source +1 ;
         top = source - 4 ;
         bottom = source +4;

enter image description here

adjacency-matrix sorting arrays algorithm javascript
1 Answers

To generate valid list of neigbours, you have to check for border crossing

col = (source - 1) % width    
if (col > 0)
   left = source - 1
if (col < width - 1)
   right = source + 1 
line = (source - 1) / width     
if (line > 0)
   top = source  - width 
if (line < height - 1)
   bottom = source + width
user_8444160
Related