Find and return all cycles given a 2D array

Question

I have an int[,] 2D array representing a house in a coordinate system. Each index is a type of enum representing building blocks, such as none=0, wall=1, stairs =2. The only part that I'm interested in this problem are the walls.

So the problem would be, given a 2D array of size NxM with marked slots like this;

//red circles represent 
array[i][k] == wall

I need to detect how many rooms there are in the grid in polynomial time. So the result would be like this,

If rooms are found the desired algorithm would return an array of lists containing the positions of each wall.

So what I'm looking for is the function "findRooms"

struct position
{
  int x,y;
}

class Room
{
    List<position> walls;
    public Room(){};
}

class Floor
{

   int[,] grid;

   //
   // The function that's needed to be implemented
   //
   public List<Room> findRooms(int[,] grid)
   {
      // given a 2D grid returns a list of rooms. 

      return Rooms;
   }

}

I thought of representing the grid as a Graph and finding all the cycles in the graph, but I felt like that was over complicating things that they already were.

An example for this in use might be terraria's building system.

I would really appreciate it if someone can shed some light on this issue.

Answer 1

You can look at Flood fill algorithm:

http://en.wikipedia.org/wiki/Flood_fill