c++ - 在知道墙壁在哪里的同时计算房间

Question

这个问题是关于 C++ builder 6 的代码。赏金对标准 C++ 算法感兴趣，以解决给定标准化输入的问题(有关更多信息，请参阅 this。)

txt 文件也表示我在数组中的数据:

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

文本说明:
txt 文件中的数字是房间墙壁的 4 位表示，设置位表示墙壁。墙位按顺时针顺序排列，最重要的位是西墙。例如，1101 代表一个房间:

• 最重要位置的设置位表示西边的墙
• 下一个最重要位置的设置位表示北方的墙
• 未设置位表示东边没有墙
• 最低位的 set 位表示南面有墙

给定:

1. 房间的外墙总会有一堵墙
2. 内墙将始终在两个房间中表示(在示例中，因为 (1, 1) 的房间是 1101 它包含一堵南面的墙，所以 (1, 2) 的房间1110 必须在北边有一堵墙
3. 永远不会超过numeric_limits<int>::max()房间

我was asked to post my code所以这里是:
我试图解决这个问题，但我遇到了 EAAccessviolation，有人可以告诉我我做错了什么吗？

  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

这是一个典型的求 connected components 总数的问题在图表中。

让我通过关注以下几点来帮助您形象化类比，请记住我们正在处理 undirected graphs在这里。

1。在图中，我们有各种顶点，如果两个顶点之间有一条边，则称这两个顶点彼此相邻。 就像您的城堡一样，如果一个单元格可以通向另一个单元格，那么两个单元格彼此相邻。

2。在图中，如果两个顶点之间存在使用边的路径，则我们有两个顶点属于同一个连通分量。 就像您的城堡一样，如果一个单元格可以沿着一条单元格路径通向另一个单元格，则两个单元格属于同一个房间号。

3。在一个图中，我们有连接的组件，这样一个连接的组件由顶点组成，这样连接组件的每两个顶点之间都有一条路径。就像我们有房间的城堡，这样每两个单元格同一个房间的单元格之间有一条路径。

现在，如果您仍然想知道如何构建图表，那么很简单。

顶点数将为 NxM(对于大小为 N 行 M 列的城堡)，等于单元格数。

只需按顺序对单元格进行编号，如果两个单元格相邻，则在单元格 a(表示顶点 a) 和 单元格 b(顶点 b) 之间有一条边。

现在可以通过在您构建的图形上应用 bfs 或 dfs 算法轻松计算房间总数。

算法在我提供的第一个链接中进行了描述。