Propagation in grid

Question

Can I do it with a lower Big O / better code? How can I improve this solution?

Task:

Let's assume we have a array like this:

1 0 0 1 0

0 0 0 0 0

0 0 0 1 0

0 0 0 0 0

1 0 0 0 0

In each turn, '1's are propagated to the neighbors(left, top, right, bottom). Return number of turns after which the whole grid will be filled with '1's.

Example of the above:

After turn 1(bold - a new '1' in the last turn):

1 1 1 1 1

1 0 0 1 0

0 0 1 1 1

1 0 0 1 0

1 1 0 0 0

After turn 2:

1 1 1 1 1

1 1 1 1 1

1 1 1 1 1

1 1 1 1 1

1 1 1 1 0

After turn 3:

1 1 1 1 1

1 1 1 1 1

1 1 1 1 1

1 1 1 1 1

1 1 1 1 1

Result: 3

My approach:

1. Collect all '1'
2. For each saved '1' propagate to all neighbors that are '0' and save newly propagated
3. Repeat 2 till nothing new appear
4. Return number of turns/generations

What is the Big O?

R - rows

C - columns

I would assume. R*C(initial discover of '1') + 4*R*C(because each number will check ones all the neighbors) = 5*RC = RC

I think it is R*C and it is linear. Am I correct?

My code(the main method contains 4 additional examples):

class Program
{
    static void Main(string[] args)
    {
        Console.WriteLine(MinimumGenerations(2, 2, new int[2,2] { { 1, 0 }, { 0, 0 } }));//result 2
        Console.WriteLine(MinimumGenerations(3, 3, new int[3,3] { { 1, 0, 0 }, { 0, 0, 0 }, { 0, 0, 0 } }));//result 4
        Console.WriteLine(MinimumGenerations(1, 1, new int[1, 1] { { 0 } }));//result -1
        Console.WriteLine(MinimumGenerations(1, 1, new int[1, 1] { { 1 } }));//result 0

        Console.ReadKey();
    }


    public static int MinimumGenerations(int rows, int columns, int[,] grid)
    {
        var toPropagate = InitialPointsToPropagate(rows, columns, grid);

        if(toPropagate.Count == 0)//whole grid was filled with '0'
        {
            return -1;
        }

        if(toPropagate.Count == rows * columns)//whole grid was filled with '1'
        {
            return 0;
        }

        var generation = 0;
        do
        {
            var toPropagateInNextGeneration = PropagateAllPoints(rows, columns, grid, toPropagate);
            if (toPropagateInNextGeneration.Any())
            {
                generation++;
                toPropagate = toPropagateInNextGeneration;
            }
        } while (toPropagate.Count > 0);

        return generation;
    }

    private static Queue<CustomPoint> PropagateAllPoints(int rows, int columns, int[,] grid, Queue<CustomPoint> toPropagate)
    {
        var toPropagateInNextGeneration = new Queue<CustomPoint>();

        while(toPropagate.Count > 0)
        {
            var pointToProcess = toPropagate.Dequeue();
            if(EmptyBottom(rows, grid, pointToProcess))
            {
                var newPoint = new CustomPoint(pointToProcess.Column, pointToProcess.Row + 1);
                grid[newPoint.Row, newPoint.Column] = 1;
                toPropagateInNextGeneration.Enqueue(newPoint);
            }

            if(EmptyLeft(grid, pointToProcess))
            {
                var newPoint = new CustomPoint(pointToProcess.Column - 1, pointToProcess.Row);
                grid[newPoint.Row, newPoint.Column] = 1;
                toPropagateInNextGeneration.Enqueue(newPoint);
            }

            if(EmptyRight(columns, grid, pointToProcess))
            {
                var newPoint = new CustomPoint(pointToProcess.Column + 1, pointToProcess.Row);
                grid[newPoint.Row, newPoint.Column] = 1;
                toPropagateInNextGeneration.Enqueue(newPoint);
            }

            if(EmptyTop(grid, pointToProcess))
            {
                var newPoint = new CustomPoint(pointToProcess.Column, pointToProcess.Row - 1);
                grid[newPoint.Row, newPoint.Column] = 1;
                toPropagateInNextGeneration.Enqueue(newPoint);
            }
        }

        return toPropagateInNextGeneration;
    }

    private static Queue<CustomPoint> InitialPointsToPropagate(int rows, int columns, int[,] grid)
    {
        var toPropagate = new Queue<CustomPoint>();

        for (var row = 0; row < rows; row++)
        {
            for(var column = 0; column < columns; column++)
            {
                if(grid[row, column] == 1)
                {
                    toPropagate.Enqueue(new CustomPoint(column, row));
                }
            }
        }

        return toPropagate;
    }

    private static bool EmptyRight(int columns, int[,] grid, CustomPoint point)
    {
        return point.Column<columns - 1 && grid[point.Row, point.Column + 1] == 0;
    }

    private static bool EmptyLeft(int[,] grid, CustomPoint point)
    {
        return point.Column > 0 && grid[point.Row, point.Column - 1] == 0;
    }

    private static bool EmptyBottom(int rows, int[,] grid, CustomPoint point)
    {
        return point.Row < rows - 1 && grid[point.Row + 1, point.Column] == 0;
    }

    private static bool EmptyTop(int[,] grid, CustomPoint point)
    {
        return point.Row > 0 && grid[point.Row - 1, point.Column] == 0;
    }
}

internal struct CustomPoint
{
    public int Row { get;  }
    public int Column { get; }

    public CustomPoint(int column, int row)
    {
        Row = row;
        Column = column;
    }
}

Answer 1

Just one remark: do not copy-paste code and then change one tiny bit of it. This indicates that you should create a method. What I mean is this:

var newPoint = new CustomPoint(pointToProcess.Column, pointToProcess.Row + 1);
grid[newPoint.Row, newPoint.Column] = 1;
toPropagateInNextGeneration.Enqueue(newPoint);

Those three lines are always the same, except the values of the parameters used in the CustomPoint constructor.

I'd create a AllPointsPropagator like this:

internal class AllPointsPropagator
{
    private static readonly Queue<CustomPoint> ToPropagateInNextGeneration = new Queue<CustomPoint>();

    public static Queue<CustomPoint> Execute(int rows, int columns, int[,] grid, Queue<CustomPoint> toPropagate)
    {
        while (toPropagate.Count > 0)
        {
            var pointToProcess = toPropagate.Dequeue();
            if (EmptyBottom(rows, grid, pointToProcess))
            {
                AddNewPoint(grid, pointToProcess.Column, pointToProcess.Row + 1);
            }

            if (EmptyLeft(grid, pointToProcess))
            {
                AddNewPoint(grid, pointToProcess.Column - 1, pointToProcess.Row);
            }

            if (EmptyRight(columns, grid, pointToProcess))
            {
                AddNewPoint(grid, pointToProcess.Column + 1, pointToProcess.Row);
            }

            if (EmptyTop(grid, pointToProcess))
            {
                AddNewPoint(grid, pointToProcess.Column, pointToProcess.Row - 1);
            }
        }

        return ToPropagateInNextGeneration;
    }

    private static void AddNewPoint(int[,] grid, int column, int row)
    {
        var newPoint = new CustomPoint(column, row);
        grid[newPoint.Row, newPoint.Column] = 1;
        ToPropagateInNextGeneration.Enqueue(newPoint);
    }

The four Empty* methods should also move to this class. Now PropagateAllPoints() can be replaced by AllPointsPropagator.Execute(rows, columns, grid, toPropagate);.