7

我正在查看一些面试问题，我偶然发现了这个：

有一个 mxn 数组。数组中的块用 1 表示，0 表示没有块。您应该找到数组中的对象数。一个对象只不过是一组水平和/或垂直连接的块。

例如

0 1 0 0
0 1 0 0
0 1 1 0
0 0 0 0
0 1 1 0

答案：这个数组中有 2 个对象。L 形对象和最后一行的对象。

我无法想出一个可以捕捉“u”（如下所示）形状的算法。我应该如何处理这个？

0 1 0 1
0 1 0 1
0 1 1 1
0 0 0 0
0 1 1 0
4

7 回答 7

3

一种方法是使用Flood Fill。该算法将是这样的：

for row in block_array:
    for block in row:
        if BLOCK IS A ONE and BLOCK NOT VISITED: 
            FLOOD_FILL starting from BLOCK

您将标记在洪水填充过程中访问过的项目，并从那里跟踪形状。

于 2013-05-01T21:02:01.903 回答
2

这适用于 C#

    static void Main()
    {
        int[][] array = { new int[] { 0, 1, 0, 1 }, new int[] { 0, 1, 0, 1 }, new int[] { 0, 1, 1, 1 }, new int[] { 0, 0, 0, 0 }, new int[] { 0, 1, 1, 0 } };
        Console.WriteLine(GetNumber(array));
        Console.ReadKey();
    }

    static int GetNumber(int[][] array)
    {
        int objects = 0;
        for (int i = 0; i < array.Length; i++)
            for (int j = 0; j < array[i].Length; j++)
                if (ClearObjects(array, i, j))
                    objects++;
        return objects;
    }

    static bool ClearObjects(int[][] array, int x, int y)
    {
        if (x < 0 || y < 0 || x >= array.Length || y >= array[x].Length) return false;
        if (array[x][y] == 1)
        {
            array[x][y] = 0;
            ClearObjects(array, x - 1, y);
            ClearObjects(array, x + 1, y);
            ClearObjects(array, x, y - 1);
            ClearObjects(array, x, y + 1);
            return true;
        }
        return false;
    }
于 2013-05-01T21:06:02.343 回答
1

我会使用不相交集（连接组件）。

开始时，每个值为 1 的 (i,j) 矩阵元素本身就是一个元素集。

然后你可以迭代每个矩阵元素，对于每个元素 (i,j) 你应该加入每个相邻的位置集 {(i+1,j),(i-1,j),(i,j+1),( i,j-1)} 到 (i,j) 如果其值为 1，则设置。

您可以在 Python中的不相交集合中找到不相交集合的实现

最后，不同集合的数量就是对象的数量。

于 2013-05-01T21:04:54.707 回答
1

我会使用不相交集数据结构（也称为联合查找）。

简而言之：对于每个连接的组件，使用每个元素的单个链接作为“父”指针来构建“反向树”。跟随父指针最终将找到树的根，用于组件标识（因为它对于连接组件的每个成员都是相同的）。要合并相邻组件，请将一个组件的根设为另一个组件的父级（不再是根，因为它现在有父级）。

两个简单的优化使这个数据结构非常高效。一种是，让所有根查询“折叠”它们的路径以直接指向根——这样，下一个查询只需要一步。另一种是，始终使用两棵树的“更深”作为新根；这需要为每个根保持一个“等级”分数。

此外，为了更有效地评估邻居，您可以考虑逐行预处理您的输入。这样，1同一行上的 's 的连续片段可以作为单个连接组件开始生命，并且您可以根据邻居标准有效地扫描前一行的片段。

于 2013-05-01T22:02:28.440 回答
1

我的两美分（斜线）算法：

1. List only the 1's.

2. Group (collect connected ones).

在哈斯克尔：

import Data.List (elemIndices, delete) 

example1 =
  [[0,1,0,0]
  ,[0,1,0,0]
  ,[0,1,1,0]
  ,[0,0,0,0]
  ,[0,1,1,0]]

example2 =
  [[0,1,0,1]
  ,[0,1,0,1]
  ,[0,1,1,1]
  ,[0,0,0,0]
  ,[0,1,1,0]]

objects a ws = solve (mapIndexes a) [] where
  mapIndexes s = 
    concatMap (\(y,xs)-> map (\x->(y,x)) xs) $ zip [0..] (map (elemIndices s) ws)
  areConnected (y,x) (y',x') =
    (y == y' && abs (x-x') == 1) || (x == x' && abs (y-y') == 1)
  solve []     r = r
  solve (x:xs) r =
    let r' = solve' xs [x]
    in solve (foldr delete xs r') (r':r)
  solve' vs r =
    let ys = filter (\y -> any (areConnected y) r) vs
    in if null ys then r else solve' (foldr delete vs ys) (ys ++ r)

输出：

*Main> objects 1 example1
[[(4,2),(4,1)],[(2,2),(2,1),(1,1),(0,1)]]
(0.01 secs, 1085360 bytes)

*Main> objects 1 example2
[[(4,2),(4,1)],[(0,3),(1,3),(2,3),(2,2),(2,1),(1,1),(0,1)]]
(0.01 secs, 1613356 bytes)
于 2013-05-02T04:22:47.507 回答
0

为什么不只查看给定块的所有相邻单元格？从其中包含 1 的某个单元格开始，跟踪您之前访问过的单元格，并继续查看相邻的单元格，直到您再也找不到 1 为止。然后移动到您尚未查看的单元格并重复该过程。

于 2013-05-01T21:00:08.030 回答
0

像这样的东西应该工作：

  1. 而数组有一个未标记的 1：
    1. 创建一个新对象
    2. 创建队列
    3. 将 1 添加到队列中
    4. 当队列不为空时：
      1. 获取队列顶部的 1
      2. 标记它
      3. 将其添加到当前对象
      4. 寻找它的 4 个邻居
      5. 如果其中任何一个是 1 并且尚未标记，则将其添加到队列中
于 2013-05-01T21:01:45.180 回答