C# – Find the Biggest Square in a Matrix – What can Excel and VBA add to it?
Finding the biggest square of specific units in a given matrix of these units is a standard dynamic programming problem. The examples in Google for it are above 18 million, thus I would simply show how it is done with C# and what is the exact steps. Then, I would solve it with Excel and VBA, to show the benefits of knowing Excel and VBA for tasks like this – it is not the speed, but the quick representation, which matters.
The C# problem:
In general, a matrix like this is given:
And the task is to answer with the biggest possible square of 1. The biggest possible square is rounded in black. It is either this one or the one, which is one row below, but the result is still the same – the side is 4.
The algorithm
- Create a second matrix with the size of the first one;
- Copy the array to a new array. Use Array.Copy to avoid copying the reference only.
- Then start looping from the second row and the second column to the left, going to the bottom right of the matrix. E.g. from the column and row with index 1, as arrays are 0-based.
- During the loop make 2 checks only:
- Write whether the element in position [r, c] is a 1.
- If it is 1, then give the minimum of the three element around it – the one on its top, the one its left and the one on its upper left diagonal. Increase that minimum with 1.
- At the end take a look at the new matrix. The highest element in it is the highest possible side. It also shows the location of that square (these are 2 in our case):
The code is here, pretty much following the algorithm:
namespace SquareInMatrix
{
using System;
class SquareInMatrix
{
static void Main()
{
int[,] matrix = new int[10, 5]
{{0, 1, 1, 0, 1},
{1, 1, 0, 1, 0},
{0, 1, 1, 1, 0},
{1, 1, 0, 1, 0},
{1, 1, 1, 1, 1},
{0, 1, 1, 1, 1},
{1, 1, 1, 1, 1},
{1, 1, 1, 1, 1},
{1, 1, 1, 1, 1},
{0, 0, 0, 0, 0}};
int rowsCount = matrix.GetLength(0);
int columnsCount = matrix.GetLength(1);
int[,] newMatrix = new int[rowsCount, columnsCount];
Array.Copy(matrix, 0, newMatrix, 0, matrix.Length);
for (int r = 1; r < rowsCount; r++)
{
for (int c = 1; c < columnsCount; c++)
{
if (matrix[r, c] == 1)
{
newMatrix[r, c] = 1 + Math.Min(newMatrix[r, c - 1],
Math.Min(newMatrix[r - 1, c],
newMatrix[r - 1, c - 1]));
}
else
{
newMatrix[r, c] = 0;
}
}
}
PrintMatrix(newMatrix);
}
public static void PrintMatrix (int[,] array)
{
int rowLength = array.GetLength(0);
int colLength = array.GetLength(1);
for (int row = 0; row < rowLength; row++)
{
for (int column = 0; column < colLength; column++)
{
Console.Write($"{array[row, column]} ");
}
Console.WriteLine();
}
}
}
}So, what can we do with Excel and VBA?
Why is it better for the representation of this algoritm? Well, just imagine the quick highlight of the exact location of the square. Plus some swap between the two matrices in real time. And this is in a real Excel file, which could be copied and pasted somewhere further. Somehow a bit fancier than a console input?
This is the code. Hope you are convinced VBA and Excel are really an iconic duo:
Option Explicit
Option Base 0
Public Function lastCol(wsName As String, Optional rowToCheck As Long = 1) As Long
Dim ws As Worksheet
Set ws = Worksheets(wsName)
lastCol = ws.Cells(rowToCheck, ws.Columns.Count).End(xlToLeft).column
End Function
Public Function lastRow(wsName As String, Optional columnToCheck As Long = 1) As Long
Dim ws As Worksheet
Set ws = Worksheets(wsName)
lastRow = ws.Cells(ws.Rows.Count, columnToCheck).End(xlUp).row
End Function
Public Sub Main()
Dim matrix As Variant
Dim rowsCount As Long
Dim columnsCount As Long
Dim newMatrix As Variant
Dim initialRange As Range
With Worksheets(1)
.Cells.ClearFormats
rowsCount = lastRow(.Name)
columnsCount = lastCol(.Name)
Set initialRange = .Range(.Cells(1, 1), .Cells(rowsCount, columnsCount))
matrix = initialRange
newMatrix = matrix
Dim biggestSize As Long
Dim biggestRow As Long
Dim biggestColumn As Long
Dim r As Long, c As Long
For r = 2 To rowsCount
For c = 2 To columnsCount
If matrix(r, c) = 1 Then
newMatrix(r, c) = 1 + Min(newMatrix(r, c - 1), newMatrix(r - 1, c), newMatrix(r - 1, c - 1))
Else
newMatrix(r, c) = 0
End If
If biggestSize < newMatrix(r, c) Then
biggestSize = newMatrix(r, c)
biggestRow = r
biggestColumn = c
End If
Next c
Next r
.Cells(rowsCount + 1, columnsCount + 1).Resize(rowsCount, columnsCount) = newMatrix
.Cells.HorizontalAlignment = xlCenter
End With
PaintBiggestSquare biggestSize, biggestRow, biggestColumn, Worksheets(1)
End Sub
Public Sub PaintBiggestSquare(biggestSize As Long, _
biggestRow As Long, _
biggestColumn As Long, _
wks As Worksheet)
With wks
Dim row As Long
Dim column As Long
For row = 0 To biggestSize - 1
For column = 0 To biggestSize - 1
.Cells(biggestRow - row, biggestColumn - column).Interior.Color = vbGreen
Next
Next
End With
End Sub
Public Function Min(ParamArray values() As Variant) As Variant
Dim minValue As Variant, Value As Variant
minValue = values(0)
For Each Value In values
If Value < minValue Then minValue = Value
Next
Min = minValue
End Function
Public Function Max(ParamArray values() As Variant) As Variant
Dim maxValue As Variant, Value As Variant
maxValue = values(0)
For Each Value In values
If Value > maxValue Then maxValue = Value
Next
Max = maxValue
End Function