Pattern matching for people who dont know algorithms - finding adjacent X's in a grid

Question

I'm wondering what the best method would be for me to approach a problem where I need to find adjacent (horizontal, vertical, diagonal) X's in a grid which is provided.

I wanted to know what the recursive way, and the nonrecursive way would be. I tried a recursive method of checking each column, and then iterating rows - that gives me X's in one direction - should I write seperate recursive functions for the other directions?

Example grid:

XXX0X 
0000X 
00X00 
XXXX0 
0000X

output should be :

(0,0),(1,0),(2,0)
(4,0),(4,1)
(2,2),(0,3),(1,3),(2,3)(3,3)

When you say "adjacent O's", do you mean pairs of O's? All O's? Only O's that touch at least one other O? — Andrew Kozak
Sorry for the confusion - I meant X's that are next to each other some how - so I would want to output all X's next to each other, or diagonal from each other — hidden name
So what you really want to do is identify the set of all X's minus the set of all X's that are not adjacent (up,down,left,right) or diagonally adjacent to another X? — Andrew Kozak

Matej Matej · Accepted Answer · 2011-11-16T15:38:20

You may want to check out the Flood Fill algorithm. You can find it on Wikipedia.

I think what you're describing is more or less it. What you do is basically:

For a given position:
If it is of the desired color (in your case 'O'):
  mark it (say, re-color it to a color 'M'),
  recurse on all desirable directions (run the same algorithm
    on new positions, which are +/-1 away);
else
  do nothing.

In your case, the result are the positions marked 'M'. If you want to find additional adjacencies, you can always reset the ones marked 'M' and start the algorithm on a different position.

EDIT: According to your examples, it seems you're looking for adjacent 'X's. :)

Pattern matching for people who dont know algorithms - finding adjacent X's in a grid

1 Answers