在知道墙壁的位置的同时计算房间

Question

这个问题是关于C++ builder 6的代码.赏金对标准C++算法感兴趣,以便在给定标准化输入的情况下解决问题(有关更多信息,请参阅此内容.)

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的说明:
txt文件中的数字是房间墙壁的4位表示,其中一个位表示墙.壁位按顺时针顺序开始,最重要的位是西墙.例如,1101代表一个房间,其中:

• 位于最重要位置的位置表示西方的一堵墙
• 下一个最重要位置的设定位表示朝向北方的墙
• 未设置的位表示没有东墙
• 位于最低位置的设置位表示南边的墙

鉴于:

1. 房间的外墙总是有一面墙
2. 内墙总是在两个房间都有表达(在这个例子中,因为(1,1)的房间是1101,它包含一个向南的墙,在(1,2)1110的房间必须包含一个向北的墙
3. 永远不会有numeric_limits<int>::max()房间

我被要求发布我的代码,所以这里是:
我试图解决这个问题,但我得到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

这是在图中查找连接组件总数的典型问题.

让我通过关注以下几点来帮助您想象这个类比,请记住我们在这里处理无向图.

1.在一个曲线图中,我们具有各种顶点和两个顶点被说成是彼此相邻的,如果在它们之间的边缘.就像你的城堡,如果一个细胞可以通往另一个细胞,那么两个细胞彼此相邻.

2.在图中,如果两个顶点之间存在使用边的路径,则我们有两个顶点属于同一个连通组件.就像你的城堡,其中两个单元格属于同一个房间号码,如果一个单元格可以通过跟随细胞的路径可以导致另一个单元格.

3.在图中,我们连接了组件,使得连接的组件由顶点组成,使得连接组件的每两个顶点在它们之间具有路径.就像我们拥有房间的城堡一样,同一房间的每两个房间都有一条细胞通道.

现在,如果您仍然想知道如何构建图表,那么它很容易.

顶点的数量将是NxM(对于大小为N行和M列的城堡),其等于单元的数量.

只需按顺序对单元格进行编号cell a(meaning vertex a),cell b(vertex b)如果两个单元格相邻,则在它们之间存在边缘.

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

该算法在我提供的第一个链接中描述.

Answer 2

老实说,我真的很想尝试解决这个问题.所以我要说你已经在这方面做出了勇敢的努力,然后继续向你展示如何做到这一点.我将假设您可以提供以下算法:

1. 以二进制读入的输入数字(因此"1101"将以十进制数"13"读入)
2. 所有这些数字都在 const vector<char> rooms
3. 可以放入每行"房间"的宽度size_t width(必须在所有行中保持一致,我们必须使用矩形房间)
4. "房间"的所有外部"墙壁"将有一个"墙"
5. 不到numeric_limits<int>::max()"房间"

我们将使用vector<int> temp标记每个房间,我们将构造它的大小rooms并将每个标签初始化为0. int result将用于标记房间,并将初始化为0.但因为所有房间标签将不会减少时更换较小的标签,size(set<int>(cbegin(temp), cend(temp)))将用于查找最终的标签计数.

我们的解决方案将围绕一个功能建立,在两个"房间"之间,没有墙; 这样:

1. 一个房间尚未标注,在这种情况下,它将采用另一个房间的标签
2. 两个房间共用一个标签,在这种情况下不会采取任何行动
3. 一个房间标签较小,在这种情况下,较大标签的所有房间将被分配较小的标签

关于这个函数的一个重要注意事项,我使用一元加运算符int从L值构造一个R值,这里有int&更多的信息.可能会使用更清晰的解决方案,但由于某些原因,Visual Studio 2015无法在此处按预期更多信息工作.static_cast<int>

void generate(vector<int>& temp, int& target, const size_t width, const size_t i) {
    const auto replacement = temp[i];

    if (target > replacement) {
        replace(begin(temp), next(begin(temp), min(size(temp), i + width - 1)), target, replacement);
    } else {
        target = replacement;
    }
}

使用此代码,我们能够:

for (size_t i = 0U; i < size(rooms); ++i) {
    const auto toWest = (rooms[i] & 0b1000) == 0;
    const auto toNorth = (rooms[i] & 0b100) == 0;
    const auto toEast = (rooms[i] & 0b10) == 0;
    const auto toSouth = (rooms[i] & 0b1) == 0;
    const auto west = toWest && temp[i - 1] != 0 ? temp[i - 1] : numeric_limits<int>::max();
    const auto north = toNorth && temp[i - width] != 0 ? temp[i - width] : numeric_limits<int>::max();
    const auto east = toEast && temp[i + 1] != 0 ? temp[i + 1] : numeric_limits<int>::max();

    temp[i] = min({ temp[i] != 0 ? temp[i] : numeric_limits<int>::max(), result + 1, west, north, east });

    if (temp[i] == result + 1) ++result;

    if (toWest) generate(temp, temp[i - 1], width, i);
    if (toNorth) generate(temp, temp[i - width], width, i);
    if (toEast) generate(temp, temp[i + 1], width, i);
    if (toSouth) temp[i + width] = temp[i];
}

Live Example