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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 |
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 |