c - 给定二维数组中的标记单元格，找到由这些标记单元格形成的重复形状

Question

给定一个二维数组，其中的单元格被标记并组合在一起形成不同的线性形状，您将如何识别重复的形状。

0010000100000000000000000000
0010000100000000000000000000
0011100100000100000000011100
0000000100000111111000000000
0010000111100100000000000000
0110000000000001111000000000
0010000100000000000000000111
0000000001000000000011110000
0000000001111110000000000000
0010000001000000000000000000

这里我们有 3 个重复的形状:
1
111111
1

111

1

到目前为止我的想法是:
为了存储形状，我将为每个形状制作树，节点结构将是

    typedef struct node{  
        struct node * leftchild;  
        struct node * rightchild;  
        struct node * downchild;  
    };  

1. 我将逐个单元格地遍历矩阵，同时维护一个 visited[][] 数组。
2. 当我找到未访问的“1”时，我将为该单元创建一个新节点并将该节点标记为该形状的根节点，因为这将是该形状要访问的第一个节点。<
3. 然后我将检查在步骤 2 中找到的根单元格的直接左、右和下单元格，并且(如果 1)将它们添加到相应根的子节点。并用这些左右和向下的单元格重复它以完成该形状的树。

在第 2 步中，我还将根元素存储在一个数组中。

现在我有每个形状的根元素。我将不得不比较数组中存在的根节点所代表的每一棵树，以找出任何重复的形状。

这个解决方案行得通吗？而且我觉得复杂性会很大。

Answer 1

是的，这会起作用。现在的问题是比较你获得的树。

例如，您可以用一串字母L,D,R,B(B 表示后退)来表示树的任何左遍历。您示例中的树将具有 'DDBRRRRRBBBBBB'、'RRBB' 和 ''(空)编码。显然，相同的树具有相同的编码，反之亦然。

现在对于每棵树，我们都有一些字符串表示。我们可以更进一步，计算该字符串的哈希值。假设我们有 H 哈希数组。现在要找到重复项，我们可以对哈希值数组进行排序，所有相同的哈希值将组合在一起。

要恢复原始形状(树)中哪些是相同的，只需要保留对树的引用和哈希，这样排序后的顺序洗牌不会造成问题。

复杂性。假设网格大小为 NxM，它包含 K 形状。树构造部分是O(N*M)(这里也散列，你可以即时计算散列)，排序O(K*logK) .假设 K=O(N*M) 将导致 O(N*M)+O(N*M*log(N*M)) = O(N*M*log (N*M)) 复杂度。一点也不大)