2

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

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 步中，我还将根元素存储在一个数组中。

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

这个解决方案会起作用吗？此外，我觉得复杂性会很大。

4

3 回答 3

2

是的，这会奏效。现在的问题是比较您获得的树木。

例如，您可以用一串字母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))复杂性。一点都不大）

于 2013-07-18T14:38:23.767 回答
1

也许您可以添加以下内容：对于每个已识别的形状，存储 1 的数量。然后，当两个形状具有相同数量的 1 时，您只需要调用（可能成本高昂的）完整比较例程。此外，第二个廉价检查将是每个形状中的行数和列数。

于 2013-07-18T14:37:38.767 回答
0

更简单的线性形状可以用一个数字表示，例如

1
111111 
1

可以根据最左一和最右一的索引表示为 111.161。最左边的索引在小数点的左边，右边的索引在小数点的右边。

右移和下移是构造一个连通分量的有效移动。其他动作生成一个列表。另一个例子

  1111
1111111
 111

可以分解为

    1111
11  11111
 1  11

这可以表示为 111.452->12.11

有间隙的类似示例

111 111
  1111

可以分解为

111     111
  1111

这可以表示为 13.36->1.3

由于数字代表图案中 1 的宽度，因此我们一次只能处理宽度最大为 9 的矩形。

111111111111

可以表示为

111111111 111

1.9->1.3

因此，每个模式都表示为浮点数列表。由于您只扫描每个元素一次，因此应该花费 O(N) 时间。要查找重复项，您只需对元素进行排序。

假设有 n 个连接的组件，其中每个组件都表示为最大 m 处的长度列表。所以总体 O(nlogn*m)。

于 2013-07-18T17:05:20.333 回答