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;
}
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
/*------ 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
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;
}
0 Comments