在数组中查找块 [英] Finding blocks in arrays

问题描述

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

I was looking over some interview questions, and I stumbled onto this one:

有一个 m x n 数组.数组中的块由 1 表示，0 表示没有块.您应该找到数组中对象的数量.一个对象只不过是一组水平和/或垂直连接的块.

There's an m x n array. A block in the array is denoted by a 1 and a 0 indicates no block. You are supposed to find the number of objects in the array. A object is nothing but a set of blocks that are connected horizontally and/or vertically.

例如

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

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

Answer: There are 2 objects in this array. The L shape object and the object in the last row.

我在想出一种可以捕捉u"(如下所示)形状的算法时遇到了麻烦.我应该如何处理这个问题?

I'm having trouble coming up with an algorithm that would catch a 'u' (as below) shape. How should i approach this?

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

推荐答案

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

这篇关于在数组中查找块的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！