一尘不染

在数组中查找块

algorithm

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

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

阅读 171

收藏
2020-07-28

共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;
    }
2020-07-28