Pages

07/02/2018

[Java] Neighbour evaluation concise logic

Here is a nice trick I was taught while doing some exercises. Consider the need to perform some loop over neighbouring places for example in an array or matrix or whatever, the basic idea would be to pick a starting point and queue up all valid points reachable from that which we did not visit yet. Assume a matrix M of size N:

A B C
D X F
G H I

And X is our starting point. We could do:

 if(i - 1 >= 0 && !visited.get(M[i - 1][j])) //do something  
 if(i - 1 >= 0 && j - 1 >= 0 && !visited.get(M[i - 1][j - 1])) //do something   
 if(i - 1 >= 0 && j + 1 < N && !visited.get(M[i - 1][j + 1])) //do something     
 if(j - 1 >= 0 && !visited.get(M[i][j - 1])) //do something  
 if(j + 1 < N && !visited.get(M[i][j + 1])) //do something  
 if(i + 1 < N && j - 1 >= 0 && !visited.get(M[i + 1][j - 1])) //do something  
 if(i + 1 < N && !visited.get(M[i + 1][j])) //do something  
 if(i + 1 < N && j + 1 < N && !visited.get(M[i + 1][j + 1])) //do something  


But here is an equivalent and more concise way of achieving the same. Consider the same matrix but focus on the changes on i and j you would do:

(-1,-1) (-1,0) (-1,+1)
(0,-1)     X   (0,+1)
(+1,-1) (+1,0) (+1,+1)

Then this can easily be converted into (and even adapted to more dimensions):

 int[] di = {-1, -1, -1, 0, 0, 1, 1, 1};  
 int[] dj = {0, -1, 1, -1, 1, -1, 0, 1};  
   
 for(int n = 0; n < di.length; n++){  
  int x = i + di[n], y = j + dj[n];  
  if(x >= 0 && x < N && y >= 0 && y < N && !visited.get(M[x][y])) //do something  
 }  

No comments:

Post a Comment

With great power comes great responsibility