Share
Explore BrainMass

C++ program to find a biggest zero submatrix

Write a C++ program to accept an n*m matrix containing only 0 and 1 values, and then find it's biggest zero submatrix i.e. the biggest submatrix in which all the values are 0.

INPUT

First line contains two numbers n, m (n,m<=300),
then n lines, each having m 0/1 digits.

OUTPUT

One number, which represent the number of zeros inside the biggest zero submatrix.

SAMPLE INPUT

6 5
0 0 0 0 0
0 1 1 1 0
0 1 0 1 0
0 1 1 1 0
0 0 0 0 0
0 0 0 0 0

SAMPLE OUTPUT

10

Solution Preview

Attached 154009.cpp provides one of the ways to solve this problem by evaluating all the sub-matrices of user input matrix for the ...

Solution Summary

Solution implements a brute force logic using recursion that redundantly evaluates many submatrices multiple times. Code compiles error and warning free with "g++ -Wall -ansi" (g++ version 3.3.1 on cygwin) and has been tested for execution with given sample input as well as various base case permutations of 1x1 and 2x2 matrices.

\$2.19