Largest Square in a Matrix of NxN - C++ Program Code

Sponsored Ads:

Quick Links

University Papers	University Syllabus	Entrance Exam
PSU Papers	Bank Papers	Placement Papers
VTU	Anna Univerity Syllabus	Anna Univerity Papers

Here is the C++ program to solve the problem of finding the largest square in a matrix of a given size NxN. Here i have put two versions of the program one which gives the matrix and other which give a Char* output as asked in TechGig coding challenge.

In the program the input is provided through a char* input array and then converted for manipulations. Please don't completely rely on my program, as i am still learning programming (always will be learning).

Suggestions are welcomed and in case you have a better program, please post it in the comment section.

Note: For Techgig code challenge you need to work on the output a bit as the testcases are not getting passed, even though the default testcase gets passed. 



C++ For TechGig Code Challange (Geekathon):

 #include string.h
#include stdio.h
#include iostream
#include string
#include sstream

using namespace std;

/* Function to get minimum of three values */
int min(int a, int b, int c)
{
    int m = a;
    if (m > b)
        m = b;
    if (m > c)
        m = c;
    return m;
}

char* biggestSquare(char* input1[])
{
    int tROW=0,tCOL=0;
    bool gotColumnCount = false;

    /*------- Get count of rows and column in a given input ------*/

    for (int i=0,COL=0;input1[i]!=NULL;i++){

        string inputData(input1[i]);
        char* c = &inputData[0];

        for (;*c;c++)
        {
            if(gotColumnCount==false && *c!='#'){
                tCOL++;
            }
        }

        gotColumnCount = true;
        tROW=i+1;
    }

    /*------ Allocating memory for matrix array -------*/

    int matrixData[50][50];


    /*------ Creating matrix array from char* -------*/

    for (int i=0;input1[i]!=NULL;i++){

        string inputData(input1[i]);
        int colCount=0;
        char* c = &inputData[0];

        for (;*c;c++)
        {
            if(*c!='#'){

                if (*c=='1'){
                    matrixData[i][colCount] = 1;
                }else{
                    matrixData[i][colCount] = 0;
                }

                //cout << "Test" << matrixData[i][colCount];
                colCount++;
            }           
        }
    }

    int sumMatrix[50][50];

    int max_of_s, max_i, max_j;

    /* Get first column */
    for(int i = 0; i < tCOL; i++)
        sumMatrix[i][0] = matrixData[i][0];

    /* Get first row */   
    for(int j = 0; j < tCOL; j++)
        sumMatrix[0][j] = matrixData[0][j];

    /* Get other entries */
    for(int i = 1; i < tROW; i++)
    {
        for(int j = 1; j < tCOL; j++)
        {
            if(matrixData[i][j] == 1)
                sumMatrix[i][j] = min(sumMatrix[i][j-1], sumMatrix[i-1][j], sumMatrix[i-1][j-1]) + 1;
            else
                sumMatrix[i][j] = 0;
        }  
    }

    /* Find the maximum entry, and indexes of maximum entry in sumMatrix */
    max_of_s = sumMatrix[0][0]; max_i = 0; max_j = 0;

    for(int i = 0; i < tROW; i++)
    {
        for(int j = 0; j < tCOL; j++)
        {
            if(max_of_s < sumMatrix[i][j])
            {
                max_of_s = sumMatrix[i][j];
                max_i = i;
                max_j = j;
            }      
        }               
    }    

    //cout << "\n Maximum size sub-matrix is: \n";

    string largeSquare;

    largeSquare = "{";

    cout << max_i  << "  " << max_of_s  << max_j << "\n";

    int reduceConst = max_j;

    for(int i = max_i; i > max_i - max_of_s; i--)
    {
        largeSquare = largeSquare + "(";

        for(int j = max_j; j > max_j - max_of_s; j--)
        {
            stringstream ss,ff;
           
            ff << max_j - j;
            ss << max_i - reduceConst;

            //cout << i << "  " << j << "\n";

            if (((i-1)==(max_i - max_of_s))&&((j-1)==( max_j - max_of_s))){               
                largeSquare = largeSquare + ss.str() + "#" + ff.str() + ")}";
            }else{
                if (((j-1)==( max_j - max_of_s))){                   
                    largeSquare = largeSquare + ss.str() + "#" + ff.str();
                }else{                   
                    largeSquare = largeSquare + ss.str() + "#" + ff.str() + ",";
                }
            }

        }
        reduceConst--;

        if ((i-1)!=(max_i - max_of_s))
            largeSquare = largeSquare + "),";
    } 

    return &largeSquare[0];
}


C++ programs for Visual Studio 2012:


#include "stdafx.h"

#include cstdio
#include iostream
#include string
#include sstream 

using namespace std;

/* UTILITY FUNCTIONS */
/* Function to get minimum of three values */
int min(int a, int b, int c)
{
    int m = a;
    if (m > b)
        m = b;
    if (m > c)
        m = c;
    return m;
}

char* biggestSquare(char* input[])
{
    int tROW=0,tCOL=0;
    bool gotColumnCount = false;

    /*------- Get count of rows and column in a given input ------*/

    for (int i=0,COL=0;input[i]!=NULL;i++){

        string inputData(input[i]);

        char* c = &inputData[0];


        for (;*c;c++)
        {
            if(gotColumnCount==false && *c!='#'){

                tCOL++;
            }
        }

        gotColumnCount = true;

        tROW=i+1;

    }

    /*------ Allocating memory for matrix array -------*/

    int **matrixData;

    matrixData=new int*[tROW]; //creates a new array of pointers to int objects

    for(int i=0; i        matrixData[i]=new int[tCOL];


    /*------ Creating matrix array from char* -------*/

    for (int i=0;input[i]!=NULL;i++){

        string inputData(input[i]);

        int colCount=0;

        char* c = &inputData[0];

        for (;*c;c++)
        {
            if(*c!='#'){

                if (*c=='1'){
                    matrixData[i][colCount] = 1;
                }else{
                    matrixData[i][colCount] = 0;
                }

                //cout << "Test" << matrixData[i][colCount];
                colCount++;
            }           
        }
    }


    int **sumMatrix;

    sumMatrix=new int*[tROW]; //creates a new array of pointers to int objects

    for(int i=0; i        sumMatrix[i]=new int[tCOL];

    int max_of_s, max_i, max_j;

    /* Set first column of S[][]*/
    for(int i = 0; i < tCOL; i++)
        sumMatrix[i][0] = matrixData[i][0];

    /* Set first row of S[][]*/   
    for(int j = 0; j < tCOL; j++)
        sumMatrix[0][j] = matrixData[0][j];

    /* Construct other entries of S[][]*/
    for(int i = 1; i < tROW; i++)
    {
        for(int j = 1; j < tCOL; j++)
        {
            if(matrixData[i][j] == 1)
                sumMatrix[i][j] = min(sumMatrix[i][j-1], sumMatrix[i-1][j], sumMatrix[i-1][j-1]) + 1;
            else
                sumMatrix[i][j] = 0;
        }  
    }


    /* Find the maximum entry, and indexes of maximum entry in S[][] */
    max_of_s = sumMatrix[0][0]; max_i = 0; max_j = 0;

    for(int i = 0; i < tROW; i++)
    {
        for(int j = 0; j < tCOL; j++)
        {
            if(max_of_s < sumMatrix[i][j])
            {
                max_of_s = sumMatrix[i][j];
                max_i = i;
                max_j = j;
            }      
        }               
    }    

    cout << "\n Maximum size sub-matrix is: \n";

    string largeSquare;

    largeSquare = "{";

    cout << max_i  << "  " << max_of_s  << max_j << "\n";

    int reduceConst = max_j;

    for(int i = max_i; i > max_i - max_of_s; i--)
    {
        largeSquare = largeSquare + "(";


        for(int j = max_j; j > max_j - max_of_s; j--)
        {
            stringstream ss,ff;

            if (((i-1)==(max_i - max_of_s))&&((j-1)==( max_j - max_of_s))){
                ff << max_j - j;
                ss << max_i - reduceConst;
                largeSquare = largeSquare + ss.str() + "#" + ff.str() + ")}";
            }else{
                if (((j-1)==( max_j - max_of_s))){
                    ff << max_j - j;
                    ss << max_i - reduceConst;
                    largeSquare = largeSquare + ss.str() + "#" + ff.str();
                }else{
                    ff << max_j - j;
                    ss << max_i - reduceConst;
                    largeSquare = largeSquare + ss.str() + "#" + ff.str() + ",";
                }
            }

        }
        reduceConst--;

        if ((i-1)!=(max_i - max_of_s))
            largeSquare = largeSquare + "),";
    } 


    cout << &largeSquare[0];

}


int _tmain(int argc, _TCHAR* argv[])
{

    char *input[10] = {"0#1#1#1#0#1#0#1","1#0#1#0#0#0#0#1","0#0#0#1#0#1#0#0","1#1#1#1#1#0#0#1","1#1#1#1#0#1#1#1","1#1#1#1#0#1#1#1","1#1#1#1#1#1#1#1","1#1#0#1#0#0#1#1"};

    biggestSquare(input);

    system("PAUSE");
    return 0;
}