# Finding blocks in arrays

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

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

One approach would use Flood Fill. The algorithm would be something like this:

```for row in block_array:
for block in row:
if BLOCK IS A ONE and BLOCK NOT VISITED:
FLOOD_FILL starting from BLOCK
```

You'd mark items visited during the flood fill process, and track shapes from there as well.

My two cents (slash) algorithm:

```1. List only the 1's.

2. Group (collect connected ones).
```

```import Data.List (elemIndices, delete)

example1 =
[[0,1,0,0]
,[0,1,0,0]
,[0,1,1,0]
,[0,0,0,0]
,[0,1,1,0]]

example2 =
[[0,1,0,1]
,[0,1,0,1]
,[0,1,1,1]
,[0,0,0,0]
,[0,1,1,0]]

objects a ws = solve (mapIndexes a) [] where
mapIndexes s =
concatMap (\(y,xs)-> map (\x->(y,x)) xs) \$ zip [0..] (map (elemIndices s) ws)
areConnected (y,x) (y',x') =
(y == y' && abs (x-x') == 1) || (x == x' && abs (y-y') == 1)
solve []     r = r
solve (x:xs) r =
let r' = solve' xs [x]
in solve (foldr delete xs r') (r':r)
solve' vs r =
let ys = filter (\y -> any (areConnected y) r) vs
in if null ys then r else solve' (foldr delete vs ys) (ys ++ r)
```

Output:

```*Main> objects 1 example1
[[(4,2),(4,1)],[(2,2),(2,1),(1,1),(0,1)]]
(0.01 secs, 1085360 bytes)

*Main> objects 1 example2
[[(4,2),(4,1)],[(0,3),(1,3),(2,3),(2,2),(2,1),(1,1),(0,1)]]
(0.01 secs, 1613356 bytes)
```