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?