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
{
    /// 
    /// Usage:
    /// 
    /// 
    /// 
    /// 
    /// 
    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 ();
            for (var i = thisM; i  m - 1)
                {
                    continue;
                }
                for (var j = thisN - 1; j  n - 1 || (i == thisM && j < 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(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
{
    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 coords)
    {
        if (coords == null)
            throw new ArgumentNullException("coords");

        Coords = coords;
    }

    public IEnumerable Coords { get; private set; }

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

Matrix

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

internal class Matrix : IEnumerable
{
    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 GetEnumerator()
    {
        for (var n = 0; n  GetEqualAdjacentCoords(Coord coord)
    {
        return GetAdjacentCoords(coord)
            .Where(a => this[a].Equals(this[coord]));
    }

    public IEnumerable 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 >= 0 && coord.N = 0 && coord.M < Columns;
    }
}

ClusterLocator

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

public class ClustersLocator : IClustersLocator
{
    private readonly T _clusterValue;

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

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

        return LocateClusters(new Matrix(matrix));
    }

    private IEnumerable LocateClusters(Matrix matrix)
    {
        var clusters = new List();
        var visited = new Matrix(matrix.Rows, matrix.Columns);

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

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

            var cluster = new ClusterBuilder(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
{
private readonly Matrix _matrix;
private readonly Matrix _visited;

public ClusterBuilder(Matrix matrix, Matrix visited)
{
_matrix = matrix;
_visited = visited;
}

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

return new Cluster(clusterCoords);

StackExchange Code Review Q#88670, answer score: 7