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

Answers


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

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). 

In Haskell:

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)

Need Your Help

Reason for the last line in CSS to not have a closing tag “;”?

css

I've been working with CSS for sometime and I see that in a lot of tutorials and exercises the last line of a CSS tag has no ";" added to it. For example:

Require https with Spring Security behind a reverse proxy

java https spring-security reverse-proxy

I have a Spring MVC application secured with Spring Security. The majority of the application uses simple http to save resources, but a small part processes more confidential information and requir...

About UNIX Resources Network

Original, collect and organize Developers related documents, information and materials, contains jQuery, Html, CSS, MySQL, .NET, ASP.NET, SQL, objective-c, iPhone, Ruby on Rails, C, SQL Server, Ruby, Arrays, Regex, ASP.NET MVC, WPF, XML, Ajax, DataBase, and so on.