Check floor congruence in 2D array in Java [closed]

Question

I'm working on a maze generation algorithm. My algorithm selects from predefined tiles and creates a maze. Here is an example produced by my code. '**' is a wall and '__' is empty floor space.

** ** ** ** ** ** ** ** ** ** ** 
** __ __ __ ** ** __ ** ** ** ** 
** ** __ __ __ __ __ ** ** ** ** 
** ** __ __ __ __ __ ** ** ** ** 
** __ __ __ ** __ ** ** ** ** ** 
** __ __ __ ** __ ** ** ** ** ** 
** __ __ ** ** __ ** ** ** ** ** 
** __ __ __ ** ** ** __ __ __ ** 
** __ ** __ ** ** ** __ __ ** ** 
** __ __ __ ** ** ** __ ** ** ** 
** ** ** ** ** ** ** ** ** ** ** 

I need to create a function that will test to see if all floor space is connected. i.e. make sure that all '__' spaces can be reached from every other '__' space. That would mean the above maze is illegal but the below is acceptable.

** ** ** ** ** ** ** ** ** ** ** 
** ** __ ** __ __ __ __ __ __ ** 
** __ __ __ __ __ __ __ __ __ ** 
** ** __ ** __ __ ** ** __ ** ** 
** __ __ __ ** ** ** __ __ __ ** 
** __ __ ** ** ** ** __ __ __ ** 
** __ __ __ ** ** ** __ __ __ ** 
** ** ** __ ** ** ** ** ** ** ** 
** __ __ __ __ __ __ ** ** ** ** 
** __ __ __ ** ** ** ** ** ** ** 
** ** ** ** ** ** ** ** ** ** ** 

I'm not sure how to best approach this problem. I think I should use a BFS search, but I'm not 100% sure. All suggestions welcome, thanks in advance!

Answer 1

Flood-fill the floors from some starting floor. You can do this either by having another 2D array just for this. You can use BFS(queue-based) or DFS(stack-based). The point is just to make an exhaustive search.

Run through the maze again. If you find any floor that hasn't been filled in the above step, we know it's not connected to the rest.