计数房间，而知道墙在哪里 [英] Counting Rooms While Knowing Where Walls Are
问题描述
这个问题是针对C ++ builder 6的代码。对于标准输入，bounty感兴趣的是标准的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 代表一个房间，其中：
- 最高有效位置的位表示墙
- 下一个最高有效位置的设置位表示向北的墙
- li>
- 最低有效位置中的设置位表示南侧的墙
：
- 房间的外墙总是有墙壁
- 将始终在两个房间中表示（在该示例中，因为在（1,1）的房间是1101 它包含一个南墙，房间在（1，2） 1110必须包含北部的墙
- 不会超过
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;
//真值检查
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 bb [i * m + j] -100 <10）||（bb [i * m + j] -100 <10） ; 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] ; 1）||（bb [i * m + j] -100 <1））
bottom = true;
// marc
if（left）
{
c [i * m + j] = c [i * m + j] + 1000; // EAaccessViolation我不知道为什么.....
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）&& [411] ++;
}
void __fastcall TForm1 :: Button7Click（TObject * Sender）
{
b1 [411] = 0;
for（int i = 0; i
b1 [i * m + j] = b [i] [j];
c [i * m + j] = b [i] [j];
}
peruse（1,1，b1）;
ShowMessage（Nr。+ IntToStr（b1 [411]））;
}
在图表中查找连接元件的总数。
让我们通过关注以下几点来帮助您可视化比较，请记住，我们正在处理无向图。
1 。在图表中，我们有多个顶点，两个顶点被认为是彼此相邻的，他们。 就像您的城堡，如果一个单元格可以连接到另一个单元格，那么两个单元格彼此相邻。
2 。在图中，如果在使用边的两个顶点之间存在路径，则具有属于同一连通分量的两个顶点。 就像您的城堡，两个单元格属于同一房间号码，如果一个单元格可以按照单元格路径导向另一个单元格。
3 。在图中我们有连接的组件，使得连接的组件由顶点组成，使得连接的组件的每两个顶点之间都有一个路径。就像你的城堡，我们有房间，这样每两个单元格
现在如果你仍然想知道如何构建图形，那么它很容易。
顶点数量将为 NxM （用于N行和M列的城堡 ）等于单元格数。
只是顺序编号单元格，并且单元格a / code>和单元格b（顶点b）。
现在，通过在您构建的图表上应用bfs或dfs算法，可以轻松计算房间总数。
该算法在第一个链接中描述我提供了。
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:
- The exterior walls of rooms will always have a wall
- 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
- 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]) );
}
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.
这篇关于计数房间，而知道墙在哪里的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
