Program Overview

This program finds the size of the largest square that can be formed using only 1s in a given binary matrix. It utilizes dynamic programming to efficiently compute the largest square at each position in the matrix.

Program Structure

• Input: A binary matrix represented as a 2D array.
• Dynamic Programming Table: A 2D array to store the size of the largest square ending at each cell.
• Output: The size of the largest square containing only 1s.

C Program

#include 

#define MAX 100

// Function to find the largest square of 1s in a binary matrix
int findLargestSquare(int matrix[MAX][MAX], int rows, int cols) {
    int dp[MAX][MAX]; // Dynamic programming table
    int maxSquareSize = 0; // Variable to store the maximum square size

    // Initialize the dynamic programming table
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            dp[i][j] = 0; // Set all entries to 0
        }
    }

    // Fill the dp table
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (matrix[i][j] == 1) { // Check if the cell is 1
                // If we're in the first row or column, just copy the value
                if (i == 0 || j == 0) {
                    dp[i][j] = 1;
                } else {
                    // Take the minimum of the top, left, and top-left diagonal values and add 1
                    dp[i][j] = (dp[i-1][j] < dp[i][j-1] ? (dp[i-1][j] < dp[i-1][j-1] ? dp[i-1][j] : dp[i-1][j-1]) : (dp[i][j-1] < dp[i-1][j-1] ? dp[i][j-1] : dp[i-1][j-1])) + 1; } // Update the maximum square size found if (dp[i][j] > maxSquareSize) {
                    maxSquareSize = dp[i][j];
                }
            }
        }
    }

    return maxSquareSize; // Return the size of the largest square
}

// Main function
int main() {
    int matrix[MAX][MAX];
    int rows, cols;

    // Input the dimensions of the matrix
    printf("Enter the number of rows and columns: ");
    scanf("%d %d", &rows, &cols);

    // Input the binary matrix
    printf("Enter the binary matrix (%d rows and %d columns):\n", rows, cols);
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            scanf("%d", &matrix[i][j]);
        }
    }

    // Find the largest square of 1s
    int largestSquare = findLargestSquare(matrix, rows, cols);
    printf("The size of the largest square containing only 1s is: %d\n", largestSquare);

    return 0;
}

Explanation of the Code

The program starts by defining a constant MAX for the maximum dimensions of the matrix. The function findLargestSquare performs the core logic:

• A dynamic programming table dp is created to store the size of the largest square ending at each cell.
• The program iterates through each cell in the input matrix. If the cell contains a 1, it checks the top, left, and top-left diagonal cells to determine the size of the largest square that can be formed up to that cell.
• After filling the dp table, the largest square size is returned.

Usage

To use the program:

1. Compile the program using a C compiler (e.g., gcc).
2. Run the executable and input the dimensions of the binary matrix.
3. Input the binary matrix values (0s and 1s).
4. The program will output the size of the largest square containing only 1s.