# Algorithm - Find groups of connected tiles

I'm terribly sorry for the title, but describing my problem with a couple of words is a tad hard. I figured the rest of the post would explain it better! ;)

**Description**

I basically have a 2D array of tiles/objects/symbols and I want to split it up into two (or more) new 2D arrays whenever a group of tiles is separated by special tiles.

For example, if I have:

**[x][x]**[0][0]

[0][0]**[x]**[0]

[0][0]**[x]**[0]

[0][0][0]**[x]**

Where the symbol x is not wanted, then that should give me two new arrays:

**[x][x]**[0][0]

**[x][x][x]**[0]

**[x][x][x]**[0]

**[x][x][x][x]**

and

**[x][x][x][x]**

[0][0]**[x][x]**

[0][0]**[x][x]**

[0][0][0]**[x]**

One array for each group of interconnecting tiles.

In my specific case, I have null objects as x, and an arbitrary object for the rest. Basically, if I can't reach tile B from tile A without crossing a null, then those two are two different groups.

I've played with it in my mind for a while, and the best I could come up with is surely far worse than O(n^2), given that they even worked in the first place. Flood fill springs to mind as something that could be used to find a group, but other than that, I'm not sure I can come up with any other similar problem to use in this instance.

**The question**

So what I'm asking is if you happen to know in which direction to take my problem and/or how to solve it. Computational complexity is not that very important since I plan not to execute this often nor on large arrays. Still, I hope i haven't hit upon a NP-hard problem! :3

Thanks!

## Answers

I hope i haven't hit upon a NP-hard problem!

This is far from being a NP problem.

I will explain two different approaches to solve the problem. One will use a Flood Fill as you expected and the other a Disjoint-set data structure.

##### Flood Fill

Let's say you have a matrix N x M where a position (row, column) is null when is not used, it contains a value otherwise.

You need to go through each column element 1..M per row 1..N. That's very simple:

for row in range(1, N + 1): for column in range(1, M + 1): if matrix[row][column] is not null: floodfill(matrix, row, column)

You will need to call the Flood Fill algorithm each time you find a non-null value, the reason will become clearer after I will define the Flood Fill method below.

def floodfill(matrix, row, column): # I will use a queue to keep record of the positions we are gonna traverse. # Each element in the queue is a coordinate position (row,column) of an element # of the matrix. Q = Queue() # A container for the up, down, left and right directions. dirs = { (-1, 0), (1, 0), (0, -1), (0, 1) } # Now we will add our initial position to the queue. Q.push( (row, column) ) # And we will mark the element as null. You will definitely need to # use a boolean matrix to mark visited elements. In this case I will simply # mark them as null. matrix[row][column] = null # Go through each element in the queue, while there are still elements to visit. while Q is not empty: # Pop the next element to visit from the queue. # Remember this is a (row, column) position. (r, c) = Q.pop() # Add the element to the output region. region.add( (r, c) ) # Check for non-visited position adjacent to this (r,c) position. # These are: # (r + 1, c): down # (r - 1, c): up # (r, c - 1): left # (r, c + 1): right for (dr, dc) in dirs: # Check if this adjacent position is not null and keep it between # the matrix size. if matrix[r + dr][c + dc] is not null and r + dr <= rows(matrix) and c + dc <= colums(matrix): # Then add the position to the queue to be visited later Q.push(r + dr, c + dc) # And mark this position as visited. matrix[r + dr][c + dc] = null # When there are no more positions to visit. You can return the # region visited. return region

You can modify this algorithm to mark each region with an specified number in a different array if you keep track of the number of regions recognized. You will notice I am using a queue instead of a recursive function, this will keep you away from hitting a maximum recursion bound limit.

##### Union-Find Algorithm

Another solution that I considered more expensive is using a Disjoint-set data structure to accomplish the same purpose. I will merely show the change to the floodfill method.

def floodfill(matrix): disjoint_set = DisjointSet() # Go through each row in the matrix for row in range(1, N + 1): # Go through each column in the matrix for column in range(1, M + 1): # Create a set for the current position disjoint_set.makeSet(row, column) if matrix[row - 1][column] is not null: # If the position north of it it is not null then merge them disjoint_set.merge((row, column), (row - 1, column)) if matrix[row][column - 1] is not null: # If the position left of it it is not null then merge them disjoint_set.merge((row, column), (row, column - 1)) # You can go through each position identifying its set and do something with it for row in range(1, N + 1): for column in range(1, M + 1): regions[ disjoint_set.find(row, column) ] = (row, column) return regions

I hope this help.

I didn't bother about showing the complexity since you didn't care about it.

It seems you need connected-component labeling algorithm to produce separated groups of objects