在数组中查找块

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