Talkative Boys & Girls

4

5 votes
Easy
Problem

Mr. Rahul is a mathematics teacher at ABC Elementary school. He is tasked with teaching a large class of 2nd grade students. The students in his class are extremely talkative and Rahul finds it very difficult to control them. One fine day he gets frustrated and decides to change the students' seating arrangement. He instructs the students to sit such that no two students of the same gender are adjacent to each other i.e. no two boys should be sitting adjacent to each other and no two girls should be sitting adjacent to each other.

The chairs in the classroom are arranged in the form of a rectangular grid. Each chair is represented by a single cell in this grid. Two chairs are adjacent if and only if their corresponding cells in the grid share a common edge. Two students are said to be sitting adjacent to each other if they are sitting on chairs which are adjacent.

The next day when he arrives at the classroom, he wants the check how well his students have followed his instructions. To do so he wants to find the area of the largest good sub-rectangle. A good sub-rectangle is defined as a sub-rectangle of the grid in which no two students of same gender are sitting adjacent to each other. Your task is to find this value given a particular arrangement of students in the classroom.

Input:

  • First line contains no. of test cases T
  • Input for T test cases follows
  • The first line of each test case contains two space separated integers n, m representing the no. of rows and no. of columns of the grid respectively.
  • The next n lines of each test case contain m sized strings of 0 s ad 1 s, representing the rows of the grid. 0 represents a boy and 1 represents a girl.

Output:

One line for each test case, containing the area of the largest good subrectangle of the input grid of the corresponding test case.

Constraints:

1 <= T <= 10

1 <= M <= 100

1 <= N <= 100

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

Sample 1 : The entire grid is of the required type.

Sample 2 : The largest possible required matrix here is just a single cell.

Sample 3 : Each rectangular subgrid is determined by a contiguous range of rows and a contiguous range of columns. The four corners of this grid do not form a valid rectangular subgrid.

Editor Image

?