CODEWITHSUNDEEP
algorithmmatrix
Ian
Ian

Reputation: 3898

Algorithm to find adjacent cells in a matrix

For example, consider a non-wraparound 4x4 matrix;

1 2 5 1 
5 2 5 2  
9 3 1 7 
2 9 0 3

If I wanted to find the neighbours of, say, the 5 in the first row = 2,5,1. Is there a more efficient solution than doing two for loops and adding a bunch of if conditions?

Upvotes: 1

Views: 1500

Answers (1)

OneRaynyDay
OneRaynyDay

Reputation: 3968

Yes. If you really need to find the neighbors, then you have an option to use graphs.

Graphs are basically vertex classes w/ their adjacent vertexes, forming an edge. We can see here that 2 forms an edge w/ 5, and 1 form an edge w/ 5, etc.

If you're going to need to know the neighbors VERY frequently(because this is inefficient if you're not), then implement your own vertex class, wrapping the value(5) in a generic T val variable. Have a hashtable of adjacent numbers and their respective distances(1 in this case, and if you need to find neighbors of 2, then you're going to need to assign those as well) by add(vertex, distance) into the hashtable.

Later on, simply iterate through the hashtable for the neighbors.

However, for an array this simple, there isn't much overhead for just doing a for loop and using "a bunch of if statements". In reality you only need to have if(boundaries check) for every direction(which is 4).

Hopefully this helps.

Upvotes: 2

Related Questions