C++ Program MS Visual Studio Given a 2D binary matrix filled with 0\'s and 1\'s,

Question

C++ Program MS Visual Studio

Given a 2D binary matrix filled with 0's and 1's, find the largest square containing all 1's and return its area. For example, given the following matrix:

1 0 1 0 0

1 0 1 1 1

1 1 1 1 1

1 0 0 1 0

Return 4

Input.txt

Your program takes as input a file with multiple test cases separated by an empty line. Each test case starts with a line with two integers indicating the size of the matrix in the test case, and is followed by lines of 0's and 1's that form the matrix. The last line is a 0 meaning the end of test cases. A sample input is as follows:

4 5

1. 0 1 0 0

1. 0 1 1 1

1. 1 1 1 1

1. 0 0 1 0

5 7

1. 0 1 0 0 1 1

1. 0 1 1 1 1 1

1. 1 1 1 1 0 1

1. 0 1 1 1 0 1

1. 0 1 0 1 0 1

0

Output

Your program should output the area for the largest square of each test case in console. The correct output for the above test cases are:

4

9

Hint

What is the objective function? Let's use f[i][j] - the side length of the largest square in matrix M[i] [j] . How would you setup a recurrence relation then?

Explanation / Answer

PLEASE REFER BELOW CODE

#include<iostream>

#include<fstream>

using namespace std;

int R,C;

int **M;

// C/C++ code for Maximum size square sub-matrix with all 1s

/* 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;

}

void printMaxSubSquare(int **M)

{

int i,j;

int max_of_s, max_i, max_j;

int **S;

S = new int*[R];

for(int i = 0; i < R; ++i)

S[i] = new int[C];

/* Set first column of S[][]*/

for(i = 0; i < R; i++)

S[i][0] = M[i][0];

/* Set first row of S[][]*/   

for(j = 0; j < C; j++)

S[0][j] = M[0][j];

/* Construct other entries of S[][]*/

for(i = 1; i < R; i++)

{

for(j = 1; j < C; j++)

{

if(M[i][j] == 1)

S[i][j] = min(S[i][j-1], S[i-1][j], S[i-1][j-1]) + 1;

else

S[i][j] = 0;

}   

}

/* Find the maximum entry, and indexes of maximum entry

in S[][] */

max_of_s = S[0][0]; max_i = 0; max_j = 0;

for(i = 0; i < R; i++)

{

for(j = 0; j < C; j++)

{

if(max_of_s < S[i][j])

{

max_of_s = S[i][j];

max_i = i;

max_j = j;

}   

}

}

cout<<(max_i * max_j)-max_of_s<<endl;

}

int main()

{

ifstream infile; //input stream for file

infile.open("test.txt"); //reading file into stream

int i = 0;

int **arr;

if(infile) //if file is present then read into array line by line else exit();

{

while(infile >> R >>C)

{

//cout<<R<<C<<endl;

//IF entry in file is 0 then we have to terminate program

if(R == 0)

break;

//creating 2d array with dimension R*C

M = new int*[R];

for(int i = 0; i < R; ++i)

M[i] = new int[C];

//reading matrix into 2D array

for(int i = 0; i < R; i++)

{

for(int j = 0; j < C; j++)

{

infile >> M[i][j];

//cout<<M[i][j]<<" ";

}

}

//calling function

printMaxSubSquare(M);

}

}

else

{

cout<<"Unable to open file"<<endl;

return 0;

}

infile.close();

getchar();

}

INPUT FILE test.txt IS

4 5
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
5 7
1 0 1 0 0 1 1
1 0 1 1 1 1 1
1 1 1 1 1 0 1
1 0 1 1 1 0 1
1 0 1 0 1 0 1
0

PLEASE REFER BELOW OUTPUT

4
9

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.