LargestSubsquareOnes.c

/*
 * Given a binary matrix, find the largest subsquare matrix.
 *
 *
 */
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>

typedef unsigned int uint;
int* getLargest(uint col, int row, uint M[][col])
{
    static int r[3] = { 0, 0, -1 };

    for (uint j = 0; j < row; j++) {
        for (uint i = 0; i < col; i++) {
            uint clen = 1, minrlen = UINT_MAX;
            int sz;

            if (M[j][i] == 1) {
                for (uint l = i + 1; l < col; l++) {

                    if (M[j][l] != 1)
                        break;

                    ++clen;

                    uint rlen = 1;
                    for (uint m = j + 1; m < row; m++) {
                        if (M[m][l] != 1)
                            break;
                        ++rlen;
                    }

                    if (rlen < minrlen)
                        minrlen = rlen;
                }
            }

            if (clen < minrlen)
                sz = (int)clen;
            else
                sz = (int)minrlen;

            if (sz > r[2]) {
                r[2] = sz;
                r[0] = j;
                r[1] = i;
            }
        }
    }

    return r;
}

int main(int argc, char** argv)
{
    uint row, col;
    scanf("%u", &row);
    printf("Row %u \n", row);
    scanf("%u", &col);

    printf("Col %u\n", col);
    uint arr[row][col];
    for (uint i = 0; i < row; i++) {
        for (uint j = 0; j < col; j++) {
            scanf("%u", &arr[i][j]);
            //printf("Arr[%d][%d]=%d",i,j,arr[i][j]);
            printf("%d ", arr[i][j]);
        }
        printf("\n");
    }
    printf("Array size %u,%u\n", row, col);
    int* r = getLargest(col, row, arr);

    printf("Largest subsquare with Ones @ %u,%u with Size %u \n", r[0], r[1], r[2]);
}