One easy way is to create an array with the size of the room and initialize it to "0". After that you should iterate over the array. If you find "0", you start the BFS from that point and color the array results in the current number.
BFS Information
BFS should look for a direct neighbor and check if there is a "0" inside this array. If so, the BFS should check to see if there is a wall between the two blocks. If there is no wall between them, paint this field with the current color (at the beginning of 1) and call BFS in a new window.
BFS automatically stops when the room is completely painted. then the global color will be increased by 1, and the cycle will continue and will look like the next "0".
After the cycle, the room count is stored inside the global color value.
this algorithm works in O (n)
A 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: BFS is being replaced with DFS, but both work.
Output
