對於三維數組對象中的連續節的C++標記

如果我們有一個3x3x3的對象數組，它包含兩個成員：一個布爾值和一個整數;任何人都可以根據布爾值提出一種將此數組標記爲連續塊的有效方法。例如，如果我們將它視爲Rubix立方體，並且缺少一箇中間切片（1，x，x == false上的所有內容），我們是否可以通過唯一的組標識將兩個外部切片標記爲單獨的組在int成員上。對於三維數組對象中的連續節的C++標記

如果「切片」經過90度，留下L形和條紋，則需要應用相同的操作。

它可以用非常大的3D數組使用遞歸嗎？它可以通過線程。

我到目前爲止打字了幾次，但已經結束了幾個死衚衕和堆棧溢出。

非常感謝任何幫助，謝謝。

來源

2011-12-18 Tradition

它可以這樣做：

struct A {int m_i; bool m_b;}; 
enum {ELimit = 3}; 
int neighbour_offsets_positive[3] = {1, ELimit, ELimit*ELimit}; 

A cube[ELimit][ELimit][ELimit]; 
A * first = &cube[0][0][0]; 
A * last = &cube[ELimit-1][ELimit-1][ELimit-1]; 

// Init 'cube'. 
for(A * it = first; it <= last; ++it) 
    it->m_i = 0, it->m_b = true; 

// Slice. 
for(int i = 0; i != ELimit; ++i) 
    for(int j = 0; j != ELimit; ++j) 
     cube[1][i][j].m_b = false; 

// Assign unique ids to coherent parts. 
int id = 0; 
for(A * it = first; it <= last; ++it) 
{ 
    if (it->m_b == false) 
     continue; 
    if (it->m_i == 0) 
     it->m_i = ++id; 
    for (int k = 0; k != 3; ++k) 
    { 
     A * neighbour = it + neighbour_offsets_positive[k]; 
     if (neighbour <= last) 
      if (neighbour->m_b == true) 
       neighbour->m_i = it->m_i; 
    } 
}

來源

2011-12-18 11:17:33 Baltram

這是相當整潔。 – sje397 2011-12-18 11:24:19

非常感謝。我會執行它，看看它是如何去並報告回來。 – Tradition 2011-12-19 08:47:05

如果我正確理解術語「連續塊」，即所有那些從每個頂點到所有其他頂點存在路徑並且它們都共享相同布爾值的數組元素的最大集合，那麼這是一個問題finding connected components in a graph這可以用一個簡單的DFS完成。想象一下，每個數組元素都是一個頂點，並且當且僅當兩個頂點連接時它們共享相同的布爾值2）它們只有一個座標不同，並且該差值爲絕對值爲1（即它們相鄰）

來源

2011-12-18 11:11:04

對於三維數組對象中的連續節的C++標記

回答

相關問題