TwoSquares | Topcoder Archive

Problem Statement

Limak has a square grid that consists of N rows by N columns of unit square cells. Each cell contains either the number 0 or the number 1. You are given the current content of Limak's grid in the String[] t. This String[] has N elements, each element has N characters, and each character is either '0' or '1'.

Limak can change the grid by performing the following operation: he can select any square part of the grid and flip all values inside the selected square (i.e., changing each 0 to a 1 and vice versa). Note that the selected square can have any position within the grid and any size, including just a single cell (a 1x1 square) and the entire grid (an NxN square).

Limak is allowed to perform the above operation zero, one, or two times. Compute and return the largest possible number of 1s in the final grid.

Definition

Class:: TwoSquares
Method:: maxOnes
Parameters:: String[]
Returns:: int
Method signature:: int maxOnes(String[] t)
(be sure your method is public)

Notes

Note the unusual Time Limit.

Constraints

N will be between 1 and 100, inclusive.
t will contain exactly N elements.
Each element in t will contain exactly N characters.
Each character in each element in t will be '0' or '1'.

Examples

```
{
"000",
"010",
"011"}
```
```
Returns: 8
```
One optimal solution is to do two operations. For the first operation Limak selects the entire square. This produces the following grid: 111 101 100 For the second operation Limak should select the 2 times 2 square in the bottom right corner of the grid. The final grid looks as follows: 111 110 111 There are 8 ones in this grid. This is the largest number of ones that can be obtained.
```
{"0"}
```
```
Returns: 1
```
Here, there is only one optimal solution. Limak should perform a single operation, flipping the only 0 to 1.
```
{
"0001",
"0001",
"0111",
"1001"}
```
```
Returns: 16
```
In this case it is possible to obtain a grid full of 1s, which is clearly optimal. One way of doing so starts by flipping the top-left 3x3 square. This produces the following grid: 1111 1111 1001 1001 Obviously, the second operation is to flip the 2x2 square in the middle of the bottom side.

{
"001111",
"111111",
"110001",
"110001",
"110001",
"111111"}

Returns: 35

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.