寻找在阵列块 [英] Finding blocks in arrays

问题描述

我一直在寻找了一些面试问题，我无意中发现了这一个：

这里有一个M×N的阵列。阵列中的一个块被表示为a 1和a 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
 

解决方案

这工作在C＃

 静态无效的主要（）
    {
        INT [] []数组= {新INT [] {0，1，0，1}，新INT [] {0，1，0，1}，新INT [] {0，1，1，1}，新INT [] {0，0，0，0}，新INT [] {0，1，1，0}};
        Console.WriteLine（GetNumber（阵列））;
        Console.ReadKey（）;
    }

    静态INT GetNumber（INT [] []数组）
    {
        INT对象= 0;
        的for（int i = 0; I＆LT; array.Length;我++）
            对于（INT J = 0; J＆LT;数组[我] .Length; J ++）
                如果（ClearObjects（阵列，I，J））
                    对象++;
        返回对象;
    }

    静态布尔ClearObjects（INT [] []数组，诠释的x，int y）对
    {
        如果（X＆LT; 0 ||Ÿ℃，|| X  -  GT; = array.Length || Y'的GT =阵列[X] .Length）返回false;
        如果（阵列[X] [Y] == 1）
        {
            数组[X] [Y] = 0;
            ClearObjects（阵列，X  -  1，Y）;
            ClearObjects（阵列，X + 1，Y）;
            ClearObjects（阵列，X，Y  -  1）;
            ClearObjects（阵列，X，Y + 1）;
            返回true;
        }
        返回false;
    }
 

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

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.

eg

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

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

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

解决方案

This works in 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屋！