one easy way would be creating an array with the size of the room and initialize it with "0".
After that you should iterate over the array. If you find a "0", you start an BFS from that point and color the array results to the current number.
Information about the BFS
The BFS has to look to the direct neighbor and check if there is a "0" inside this array. If this is true, the BFS has to check if there are no wall between the two boxes. If there is no wall in between, color this box with the current color (at the beginning 1) and call the BFS on the new box.
The BFS stops automaticly when the room is completely colored. then the global color will be increased by 1 and the loop continues and looks for the next "0".
After the loop the count of the rooms is stored inside the global color value.
this algorithm works in O(n)
Small example:
//CountingRooms.h
#include <vector>
class CountingRooms
{
public:
CountingRooms();
~CountingRooms();
int Count();
void TestFill();
void Print();
private:
struct Point
{
int x = 0;
int y = 0;
};
unsigned int* m_arrFieldColors = nullptr;
unsigned int* m_arrFieldWalls = nullptr;
int m_nSizeX = 0;
int m_nSizeY = 0;
int m_nCurrentColor = 0;
unsigned int GetValue(unsigned int* field, int x, int y);
void SetValue(unsigned int* field, int x, int y, unsigned int value);
bool CanPass(int x1, int y1, int x2, int y2);
void DFS(int posX, int posY);
bool IsInsideArray(int x1, int y1);
};
//CountingRooms.cpp
#include "stdafx.h"
#include "CountingRooms.h"
#include <iostream>
CountingRooms::CountingRooms()
{
}
CountingRooms::~CountingRooms()
{
if (m_arrFieldColors)
{
delete[]m_arrFieldColors;
}
if (m_arrFieldWalls)
{
delete[]m_arrFieldWalls;
}
}
bool CountingRooms::IsInsideArray(int x, int y)
{
return x >= 0 && y >= 0 && x < m_nSizeX && y < m_nSizeY;
}
bool CountingRooms::CanPass(int x1, int y1, int x2, int y2)
{
if (IsInsideArray(x1, y1) && IsInsideArray(x2, y2)) //inside the array range
{
if (x2 - x1 == 1 && y2 - y1 == 0) // right
{
if (!(GetValue(m_arrFieldWalls, x1, y1) & 2) && !(GetValue(m_arrFieldWalls, x2, y2) & 8)) { return true; }
}
if (x2 - x1 == 0 && y2 - y1 == -1) // up
{
if (!(GetValue(m_arrFieldWalls, x1, y1) & 4) && !(GetValue(m_arrFieldWalls, x2, y2) & 1)) { return true; }
}
if (x2 - x1 == -1 && y2 - y1 == 0) // left
{
if (!(GetValue(m_arrFieldWalls, x1, y1) & 8) && !(GetValue(m_arrFieldWalls, x2, y2) & 2)) { return true; }
}
if (x2 - x1 == 0 && y2 - y1 == 1) // down
{
if (!(GetValue(m_arrFieldWalls, x1, y1) & 1) && !(GetValue(m_arrFieldWalls, x2, y2) & 4)) { return true; }
}
}
return false;
}
void CountingRooms::DFS(int posX, int posY)
{
if (GetValue(m_arrFieldColors, posX, posY)) // check if the field is already colored
{
return;
}
Point sStart;
sStart.x = posX;
sStart.y = posY;
std::vector<Point> vecList;
vecList.push_back(sStart);
m_nCurrentColor++;
while (vecList.size()) // as long as something is inside the list
{
Point sTemp = vecList[vecList.size()-1]; //get out the last element
vecList.pop_back();
if (IsInsideArray(sTemp.x, sTemp.y))
{
if (!GetValue(m_arrFieldColors, sTemp.x, sTemp.y)) // is field not colored
{
SetValue(m_arrFieldColors, sTemp.x, sTemp.y, m_nCurrentColor);
if (CanPass(sTemp.x, sTemp.y, sTemp.x + 1, sTemp.y)) /* right*/
{
Point newPoint;
newPoint.x = sTemp.x + 1;
newPoint.y = sTemp.y;
vecList.push_back(newPoint);
}
if (CanPass(sTemp.x, sTemp.y, sTemp.x - 1, sTemp.y)) /* left*/
{
Point newPoint;
newPoint.x = sTemp.x - 1;
newPoint.y = sTemp.y;
vecList.push_back(newPoint);
}
if (CanPass(sTemp.x, sTemp.y, sTemp.x, sTemp.y - 1)) /* up*/
{
Point newPoint;
newPoint.x = sTemp.x;
newPoint.y = sTemp.y - 1;
vecList.push_back(newPoint);
}
if (CanPass(sTemp.x, sTemp.y, sTemp.x, sTemp.y + 1)) /* down*/
{
Point newPoint;
newPoint.x = sTemp.x;
newPoint.y = sTemp.y + 1;
vecList.push_back(newPoint);
}
}
}
}
}
int CountingRooms::Count()
{
m_nCurrentColor = 0;
for (int i = 0; i < m_nSizeY; ++i)
{
for (int j = 0; j < m_nSizeX; ++j)
{
DFS(j, i);
}
}
return m_nCurrentColor;
}
void CountingRooms::TestFill()
{
m_arrFieldWalls = new unsigned int[42]{13, 6,13, 6,12, 5, 6,
14, 9, 6,11,10,15,10,
8, 5, 3,14,11,14,10,
11,13, 5, 1, 5, 3,11};
m_arrFieldColors = new unsigned int[42];
for (int i = 0; i < 42;i++)
{
m_arrFieldColors[i] = 0;
}
m_nSizeX = 7;
m_nSizeY = 4;
}
unsigned int CountingRooms::GetValue(unsigned int* field, int x, int y)
{
if (IsInsideArray(x, y))
{
return field[x + m_nSizeX*y];
}
return -1;
}
void CountingRooms::SetValue(unsigned int* field, int x, int y, unsigned int value)
{
if (IsInsideArray(x, y))
{
field[x + m_nSizeX*y] = value;
}
}
void CountingRooms::Print()
{
std::cout << "Walls:" << std::endl;
for (int j = 0; j < m_nSizeY;++j)
{
for (int i = 0; i < m_nSizeX;++i)
{
std::cout << GetValue(m_arrFieldWalls, i, j) << "\t";
}
std::cout << std::endl;
}
std::cout << std::endl<<"Colors:" << std::endl;
for (int j = 0; j < m_nSizeY;++j)
{
for (int i = 0; i < m_nSizeX;++i)
{
std::cout << GetValue(m_arrFieldColors, i, j) << "\t";
}
std::cout << std::endl;
}
}
//main.cpp
#include "stdafx.h"
#include <iostream>
#include "CountingRooms.h"
int main()
{
CountingRooms cr;
cr.TestFill();
std::cout<<"There are "<<cr.Count()<<" rooms"<<std::endl;
cr.Print();
char key = 0;
std::cin >> key;
return 0;
}
btw: the BFS is replaced by a DFS, but both is working.
Output
