Get a Rectangular Field
InterviewTime limit2sMemory limit512 MB
For each 5x5 grid of 0s and 1s, report the largest number of 1s contained in an all-ones axis-aligned rectangle.
- Level
Medium5 of 10
- Topics
- Brute force, Array, Implementation, Prefix sum
- Solved
- No attempts yet
Problem
Karnaugh is a poor farmer with a very small field. He wants to reclaim wasteland in the kingdom to get a new field. But the king, who loves regular shapes, made a rule that a settler can receive only a rectangular piece of land as a field. So Karnaugh must obtain the largest rectangular land suitable for reclamation.
The wasteland map is given as a 5 x 5 grid, as in the figures below, where '1' marks a place suitable for reclamation and '0' marks a sandy place. Find the largest rectangle made up only of 1's in the map and report its size. The size of a rectangle is the number of 1's it contains. There may be two or more largest rectangles of the same size.
Figure 1. The size of the largest rectangles is 4. There are two largest rectangles (shaded).
Figure 2. The size of the largest rectangle is 3. There is one largest rectangle (shaded).
Input
The input consists of maps preceded by an integer m giving the number of maps.
m
map1
map2
map3
...
mapm
Two maps are separated by an empty line.
Each map**k has the following format.
p p p p p
p p p p p
p p p p p
p p p p p
p p p p p
Each p is a character, either '1' or '0'. Two p's on the same line are separated by a space character. Here the character '1' marks a place suitable for reclamation and '0' marks a sandy place. Each map contains at least one '1'.
Output
For each input map, print the size of the largest rectangle on a separate line.