Finding clusters in a matrix I got asked at an interview to write a program that, given a NxM matrix with zeros and ones, prints out the list of clusters of 1s. The clusters are defined as patches of 1s connected horizontally, vertically or diagonally.

Here's the code I submitted but I'm wondering if there is a better way, e.g. a well-known algorithm to produce the solution.

namespace ConsoleApplication1
{
    /// &lt;summary&gt;
    /// Usage:
    /// &lt;![CDATA[
    /// 
    ///            var m = 4; // rows
    ///            var n = 5; // cols
    ///            var matrix = new[]
    ///            {
    ///                0,1,0,0,0,  // 0-4
    ///                0,0,1,1,0,  // 5-9
    ///                0,0,0,0,0,  // 10-14
    ///                0,1,1,0,0   // 15-19
    ///            };
    ///
    ///            var finder = new MatrixClusterFinder(matrix, m, n);
    ///            finder.PrintClusters();
    /// PRINTS:
    /// (0,1)(1,2)(1,3)
    /// (3,1)(3,2)
    /// 
    /// ]]&gt;
    /// 
    /// 
    /// 
    /// &lt;/summary&gt;
    public class MatrixClusterFinder
    {
        private int m;
        private int n;
        private int[] matrix;

        public MatrixClusterFinder(int[] matrix, int m, int n)
        {
            this.m = m;
            this.n = n;
            this.matrix = matrix;
        }

        public void PrintClusters()
        {
            var visited = new bool[m * n];

            for (var i = 0; i &lt; m * n; i++)
            {
                var isClusterFound = Traverse(i, visited);

                if (isClusterFound)
                {
                    Console.WriteLine(); //crlf
                }
            }

        }

        private bool Traverse(int curr, bool[] visited)
        {
            if (visited[curr])
            {
                return false;
            }

            bool result = false;
            visited[curr] = true;
            if (matrix[curr] == 1)
            {
                result = true;
                var thisM = curr / n;
                var thisN = curr % n;
                Console.Write("({0},{1})", thisM, thisN);

                var adjs = GetAdjacent(curr);
                foreach (var adj in adjs)
                {
                    Traverse(adj, visited);
                }
            }
            return result;
        }

        private int[] GetAdjacent(int curr)
        {
            var thisM = curr / n;
            var thisN = curr % n;
            var result = new List&lt;int&gt;();
            for (var i = thisM; i &lt;= thisM + 1; i++)
            {
                if (i &lt; 0 || i &gt; m - 1)
                {
                    continue;
                }
                for (var j = thisN - 1; j &lt;= thisN + 1; j++)
                {
                    if (j &lt; 0 || j &gt; n - 1 || (i == thisM &amp;&amp; j &lt; thisN))
                    {
                        continue;
                    }
                    var res = i * n + j;
                    if (res == curr)
                    {
                        continue;
                    }
                    result.Add(res);
                }
            }
            return result.ToArray();
        }

    }
}
For a problem like this, the interviewer is not actually looking for the most efficient/well-known algorithm possible. They want you to demonstrate that you can solve simple problems, using OO principles (encapsulation, inheritance, polymorphism), C# language features (Generics, LINQ, TPL etc) as well as industry standard patterns and practices like TDD, SOLID, DRY and so on.

The solution you have written is good in that it solves the problem and correctly uses recursion (probably eliminating 90% of the competition). I had some spare time today, so I've written an alternative solution that demonstrates some of the things I just mentioned. It is by no means, "the answer", just one of many possible solutions.

class Program
{
    static void Main()
    {
        var input = new[,]
        {
            {0, 1, 0, 0, 0},
            {0, 0, 1, 1, 0},
            {0, 0, 0, 0, 0},
            {0, 1, 1, 0, 0}
        };

        var locator = new ClustersLocator&lt;int&gt;(1);
        var clusters = locator.LocateClusters(input);

        foreach (var cluster in clusters)
            Console.WriteLine(cluster);

        Console.ReadKey();
    }
}




Coord

A 2D coordinate (struct) used by Matrix and Cluster.

public struct Coord : IEquatable&lt;Coord&gt;
{
    public Coord(int n, int m) : this()
    {
        N = n;
        M = m;
    }

    public int N { get; private set; }
    public int M { get; private set; }

    #region ToString() and Equals()
}


Cluster

A list of Coords that is equal to another Cluster if it has the same Coords.

public class Cluster
{
    public Cluster(IEnumerable&lt;Coord&gt; coords)
    {
        if (coords == null)
            throw new ArgumentNullException("coords");

        Coords = coords;
    }

    public IEnumerable&lt;Coord&gt; Coords { get; private set; }

    // Override Equals() and GetHashCode() to compare Coords
    #region Equals() and ToString()
}


Matrix

A 2D matrix of generic values. Implements IEnumerable&lt;Coord&gt; to allow for easy enumeration of all coordinates. Contains helper methods for getting adjacent coordinates.

internal class Matrix&lt;T&gt; : IEnumerable&lt;Coord&gt;
{
    private readonly T[,] _values;

    public Matrix(T[,] values)
    {
        _values = values;
    }

    public Matrix(int rows, int columns)
    {
        _values = new T[rows, columns];
    }

    public T this[Coord coord]
    {
        get { return _values[coord.N, coord.M]; }
        set { _values[coord.N, coord.M] = value; }
    }

    public int Rows { get { return _values.GetLength(0); } }
    public int Columns { get { return _values.GetLength(1); } }

    public IEnumerator&lt;Coord&gt; GetEnumerator()
    {
        for (var n = 0; n &lt; Rows; n++)
            for (var m = 0; m &lt; Columns; m++)
                yield return new Coord(n, m);
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }

    public IEnumerable&lt;Coord&gt; GetEqualAdjacentCoords(Coord coord)
    {
        return GetAdjacentCoords(coord)
            .Where(a =&gt; this[a].Equals(this[coord]));
    }

    public IEnumerable&lt;Coord&gt; GetAdjacentCoords(Coord coord)
    {
        var adjacent = new[]
        {
            new Coord(coord.N - 1, coord.M + 1),
            new Coord(coord.N - 1, coord.M),
            new Coord(coord.N - 1, coord.M - 1),
            new Coord(coord.N + 1, coord.M + 1),
            new Coord(coord.N + 1, coord.M),
            new Coord(coord.N + 1, coord.M - 1),
            new Coord(coord.N, coord.M + 1),
            new Coord(coord.N, coord.M - 1)
        };

        return adjacent.Where(InRange);
    }

    public bool InRange(Coord coord)
    {
        return coord.N &gt;= 0 &amp;&amp; coord.N &lt; Rows
            &amp;&amp; coord.M &gt;= 0 &amp;&amp; coord.M &lt; Columns;
    }
}


ClusterLocator

The main algorithm. Also generic, and can locate clusters of any value.

public class ClustersLocator&lt;T&gt; : IClustersLocator&lt;T&gt;
{
    private readonly T _clusterValue;

    public ClustersLocator(T clusterValue)
    {
        _clusterValue = clusterValue;
    }

    public IEnumerable&lt;Cluster&gt; LocateClusters(T[,] matrix)
    {
        if (matrix == null)
            throw new ArgumentNullException("matrix");

        return LocateClusters(new Matrix&lt;T&gt;(matrix));
    }

    private IEnumerable&lt;Cluster&gt; LocateClusters(Matrix&lt;T&gt; matrix)
    {
        var clusters = new List&lt;Cluster&gt;();
        var visited = new Matrix&lt;bool&gt;(matrix.Rows, matrix.Columns);

        foreach (var coord in matrix.Where(c =&gt; !visited[c]))
        {
            visited[coord] = true;

            if (!matrix[coord].Equals(_clusterValue))
                continue;

            var cluster = new ClusterBuilder&lt;T&gt;(matrix, visited).Build(coord);
            clusters.Add(cluster);
        }
        return clusters;
    }
}


ClusterBuilder

The recursive part of the algorithm. Uses a Matrix and a single member of a cluster to locate the other members in the same cluster.

internal class ClusterBuilder&lt;T&gt;
{
    private readonly Matrix&lt;T&gt; _matrix;
    private readonly Matrix&lt;bool&gt; _visited;

    public ClusterBuilder(Matrix&lt;T&gt; matrix, Matrix&lt;bool&gt; visited)
    {
        _matrix = matrix;
        _visited = visited;
    }

    public Cluster Build(Coord seed)
    {
        var clusterCoords = new List&lt;Coord&gt; {seed};
        Build(clusterCoords, seed);

        return new Cluster(clusterCoords);
    }

    private void Build(List&lt;Coord&gt; cluster, Coord current)
    {
        _visited[current] = true;

        var nextCoords = _matrix.GetEqualAdjacentCoords(current)
            .Where(c =&gt; !_visited[c]);

        foreach (var next in nextCoords)
        {
            cluster.Add(next);
            Build(cluster, next);
        }
    }
}


And most importantly, tests for the public API!

[TestFixture]
public class ClusterLocatorTests
{
    [Test]
    public void Throws_if_matrix_is_null()
    {
        var sut = new ClustersLocator&lt;int&gt;(1);

        Assert.Throws&lt;ArgumentNullException&gt;(() =&gt; sut.LocateClusters(null));
    }

    [Test]
    public void Returns_empty_collection_if_matrix_is_empty()
    {
        var sut = new ClustersLocator&lt;int&gt;(1);

        var clusters = sut.LocateClusters(EmptyMatrix);

        Assert.That(clusters, Is.Empty);
    }

    [TestCaseSource("GetLocatesClustersTestCases")]
    public void Locates_clusters(int[,] matrix, IEnumerable&lt;Cluster&gt; expectedClusters)
    {
        var sut = new ClustersLocator&lt;int&gt;(1);

        var clusters = sut.LocateClusters(matrix);

        Assert.That(clusters, Is.EqualTo(expectedClusters));
    }

    private static IEnumerable&lt;ITestCaseData&gt; GetLocatesClustersTestCases()
    {
        var testCase1 = new TestCaseData(Matrix1, Clusters1);
        testCase1.SetName("Large matrix of mixed clusters");

        // Add more test cases as needed
        return new[] {testCase1};
    }

    #region Test data
}