在数组中查找块

Question

我正在寻找一些面试问题，但偶然发现了一个问题：

有一个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

Answer 1

这在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;
    }