在数组中查找块

我正在查看一些面试问题，并且我偶然发现了这一个：在数组中查找块

有一个m×n数组。数组中的块用1表示，而0表示无块。你应该找到数组中的对象的数量。一个对象只不过是一组水平和/或垂直连接的块。

例如

答案：有此阵列中的2个对象。 L形对象和最后一行中的对象。

我有麻烦想出一个算法，可以捕捉'u'（如下）形状。我应该如何处理这个问题？

来源

2013-05-01 Lg102

你或许可以使用[颜色填充]（HTTP：// en.wikipedia.org/wiki/Flood_fill）查找形状。扫描（未访问）1并在您找到它时填充该形状。 – thegrinner 2013-05-01 20:57:53

所以对角线不被认为是有效的连接？ – 2013-05-01 21:39:41

不，他们不是。 – Lg102 2013-05-01 21:42:46

这个工作在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-01 21:06:02

这不断循环，但我不知道为什么。 – Lg102 2013-05-01 21:37:48

@ Lg102我继续测试它的真实性，该错误可能在for循环中，他们都在做我++>< – 2013-05-01 21:46:24

Jep，我也只是接触到了那个。我已经运行了上述代码的改编，并且效果很好。谢谢。 – Lg102 2013-05-01 21:53:10

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

来源

2013-05-01 21:00:08 Calpis

像这样的东西应该工作：

而阵列具有不是标志着一个1：
1. 创建一个新的对象
2. 创建队列
3. 1添加到队列
4. 虽然队列不为空：
  1. 获得队列顶部的1
  2. 将其标记
  3. 将它添加到当前对象
  4. 寻找它的4个相邻
  5. 如果其中任何一个1和未标示的是，将其添加到队列

来源

2013-05-01 21:01:45 iluxa

一种方法将使用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-01 21:02:01 thegrinner

该算法的运行时间是什么？ – 2013-10-29 04:42:34

@ Myth17我发布的不太安全的洪水填充将是'O（mn）'。我不确定实际的洪水填充情况 - 它显然取决于底层的实现，并且有一些聪明的事情可以改进。 – thegrinner 2013-10-29 14:13:01

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

开始时，值为1的每个（i，j）矩阵元素都是一个元素集合。（i + 1，j），（i-1，j），（i，j + 1），则可以迭代每个矩阵元素并为每个元素1），（I，J-1）}，以（I，J）设定其值为1。

，可以看到在Disjoint Sets in Python

不相交的集合的执行在结束时，不同势的数集合是对象的数量。

来源

2013-05-01 21:04:54

我会用一个disjoint-set datastructure（也称为合并 - 查找）。

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

两个简单的优化使该数据结构非常有效。一个是，让所有的根查询“崩溃”他们的路径直接指向根 - 这样，下一个查询将只需要一个步骤。另一种是，总是使用两棵树的“更深”作为新的根;这需要维护每个根的“排名”分数。

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

来源

2013-05-01 22:02:28 comingstorm

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

1. List only the 1's. 

2. Group (collect connected ones).

在Haskell：

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-02 04:22:47

没有解释的downvote只是意味着什么。 – 2016-07-16 13:52:09

在数组中查找块

回答

相关问题