Finding blocks in arrays

algorithm, arrays, multidimensional-array

Solution

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

Problem

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 ```

Original source