c++ - Counting Rooms While Knowing Where Walls Are

Question

This question is on code for C++ builder 6. The bounty is interested in a standard C++ algorithm to solve the problem given a standardized input (see this for more information.)

The txt file which also represents the data I have in an array:

1101 0110 1101 0110 1100 0101 0110
1110 1001 0110 1011 1010 1111 1010
1000 0101 0011 1110 1011 1110 1010
1011 1101 0101 0001 0101 0011 1011

Explanation of the txt:
The numbers from the txt file are a 4-bit representation of the walls to a room, with a set bit representing a wall. The wall bits are in clockwise order starting with the most significant bit being the West wall. For example, 1101 represents a room where:

• The set bit in the most significant position indicates a wall to the West
• The set bit in the next most significant position indicates a wall to the North
• The unset bit indicates no wall to the East
• The set bit in the least significant position indicates a wall to the South

Given:

1. The exterior walls of rooms will always have a wall
2. Interior walls will always be expressed in both rooms (in the example since the room at (1, 1) is 1101 it contains a wall to the South, the room at (1, 2) 1110 must contain a wall to the North
3. There will never be more than numeric_limits<int>::max() rooms

I was asked to post my code so here it is:
I've tried to solve this but I'm getting an EAAccessviolation can someone tell me what I'm doing wrong?

  int rn=0,z=0, global=0,coord[15],c[411],b1[411];

void peruse ( int i, int j,int* bb)
{
bool top=false,bottom=false,right=false,left=false;
//truth checks

if (bb[i*m+j]<1000)  left=true;

if (bb[i*m+j]<100)   top=true; else if (bb[i*m+j]-1000<100)   top=true;

if (bb[i*m+j]<10)    right=true; else
if ( (bb[i*m+j]-100<10) || (bb[i*m+j]-1000<10) || (bb[i*m+j]-100<10) ) right=true;

if (bb[i*m+j]<1)   bottom=true; else
if ( (bb[i*m+j]-10<1) || (bb[i*m+j]-100<1) || (bb[i*m+j]-1000<1) ||(bb[i*m+j]-100<1))
bottom=true;
//marc

if  (left)
{
c[i*m+j]=c[i*m+j]+1000; // EAaccessViolation i dont know why.....
peruse(i,j-1,c);
}
if (top)
{
c[i*m+j]=c[i*m+j]+100;
peruse(i-1,j,c);
}
if (right)
{
c[i*m+j]=c[i*m+j]+10;
peruse(i,j+1,c);
}
if (bottom)
{
c[i*m+j]=c[i*m+j]+1;
peruse(i+1,i,c);
}
 if ( !(left) && !(top) && !(right) && !(bottom) )
 {
  bb[411]++;



 }
}


void __fastcall TForm1::Button7Click(TObject *Sender)
{
b1[411]=0;

 for(int i=0;i<n;i++)
    for (int j=0;j<m;j++)
          {
           b1[i*m+j]=b[i][j];
           c[i*m+j]=b[i][j];
          }
  peruse (1,1,b1);

 ShowMessage("Nr. "+IntToStr(b1[411]) );
}

Answer 1

This is a typical problem of finding the total number of connected components in a graph.

Let me help you visualize the analogy by focusing on following points, keeping in mind that we are dealing with undirected graphs here.

1.In a graph, we have various vertices and two vertices are said to be adjacent to each other, if there is an edge between them. Just like your castle where two cells are adjacent to each other if one cell could lead to another cell.

2. In a graph we have two vertices belong to the same connected component, if there is a path between two vertices using the edges. Just like your castle where two cells belong to the same room number if one cell can by following a path of cells could lead to another.

3. In a graph we have connected components, such that a connected component is made up of vertices such that every two vertices of the connected component have a path between them.Just like your castle where we have rooms, such that every two cells of the same room have a path of cells between them.

Now if you are still wondering how to build the graph, well its easy.

The number of vertices will be NxM(for a castle of size N rows and M columns) which is equal to the number of cells.

Just number the cells sequentially and there is an edge between cell a(meaning vertex a) and cell b(vertex b) if both cells are adjacent.

Now the total number of rooms can be easily counted by applying bfs or dfs algorithm on your graph that you build.

The algorithm is described in the first link I provided.