The search for effective answers to a variety of problems in computer science and algorithmic problem-solving frequently brings us to fascinating riddles with combinatorial logic at their core. One such problem is figuring out how big the largest plus sign ('+') in a binary matrix that is made up only of one's is. Envision a two-dimensional binary grid where every cell has the potential to be either 0 or 1. Our goal is to find the largest cross-like structure ('+') made entirely of one's own. There are a few requirements this structure must meet: its arms must reach both vertically and horizontally, with the intersection point represented by a central cell. Moreover, the plus sign's arms cannot cross over or reach outside the matrix's bounds.
Example:
0 1 1
1 1 1
0 1 0
Output:
Approach:
A simple answer to the problem is to determine the largest "+", which requires figuring out the maximum number of 1s in one direction for a point in the matrix that must be the same for a given 1 in all four directions. We will do this by making a single matrix, or 4, for each side of the point. For the given element, each will record the total number of consecutive 1s. We will determine the maximum value, which is the lowest of all subsequent values in each of the four directions, for each index value.
Example 1:
Let us take a C++ program to find the size of the largest '+' formed by all 1's in a given binary matrix.
#include <iostream>
using namespace std;
// Size of the binary square matrix
#define N 5
// Function to find the size of the largest '+'
int findLargestPlus(int mat[N][N]) {
// Arrays to store maximum consecutive 1's to the left, right, top, and bottom of each cell
int left[N][N], right[N][N], top[N][N], bottom[N][N];
// Initialize the arrays
for (int i = 0; i < N; i++) {
top[0][i] = mat[0][i];
bottom[N - 1][i] = mat[N - 1][i];
left[i][0] = mat[i][0];
right[i][N - 1] = mat[i][N - 1];
}
// Fill the arrays
for (int i = 0; i < N; i++) {
for (int j = 1; j < N; j++) {
if (mat[i][j] == 1)
left[i][j] = left[i][j - 1] + 1;
else
left[i][j] = 0;
if (mat[j][i] == 1)
top[j][i] = top[j - 1][i] + 1;
else
top[j][i] = 0;
j = N - 1 - j;
if (mat[j][i] == 1)
bottom[j][i] = bottom[j + 1][i] + 1;
else
bottom[j][i] = 0;
if (mat[i][j] == 1)
right[i][j] = right[i][j + 1] + 1;
else
right[i][j] = 0;
j = N - 1 - j;
}
}
// Find the size of the largest '+'
int max_size = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
int min_len = left[i][j];
min_len = min_len < right[i][j] ? min_len : right[i][j];
min_len = min_len < top[i][j] ? min_len : top[i][j];
min_len = min_len < bottom[i][j] ? min_len : bottom[i][j];
if (min_len > max_size)
max_size = min_len;
}
}
// Calculate the total size of the largest '+'
if (max_size)
return 4 * (max_size - 1) + 1;
return 0;
}
/* Driver function */
int main() {
// Binary Matrix of size N
int mat[N][N] = {
{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}
};
// Find and print the size of the largest '+'
cout << "Size of the largest '+' formed by all 1's: " << findLargestPlus(mat) << endl;
return 0;
}
Output:
Size of the largest '+' formed by all 1's: 9
Explanation:
This C++ program's objective is to figure out how big the largest plus sign ('+') in a given binary matrix is when it only contains ones. After that, it initializes arrays first and stores the maximum consecutive ones to the left, right, top, and bottom of each cell in the matrix. These arrays are filled by iterating through the matrix and updating the counts of ones that follow in each direction. At Last, using the central cell and four arms of length (n - 1) in each direction, the program determines and returns the size of the largest plus sign. Returning zero means that there isn't a plus sign to be found, meaning that the maximum size is zero.