CuttingPaper | Topcoder Archive

Problem Statement

You have a piece of paper that is divided into multiple sections with different colors, and you want to cut it into several pieces that each contain only a single color. You want the resulting pieces to be as big as possible, so you will never cut through a single-colored section. You will only make cuts along lines that separate sections with different colors.

A single cut is done in the following way: First, position the cutter on some point on the paper that is not completely surrounded by paper (in other words, a point on an edge). Then, perform a continuous cut until you touch some other point that is not completely surrounded by paper. This entire action counts as a single cut. Note that as soon as a point becomes part of a cut, it is no longer considered to be a point completely surrounded by paper. Therefore, a cut can never cross itself (see example 5). Also note that a cut does not need to be a straight line.

You will be given the paper as a String[], where the j^th character of the i^th element represents the square at row i, column j. A space character means that there is no paper in that square, and each uppercase letter represents a different color. Return the minimum number of cuts (as described above) needed to accomplish this task. If it is impossible, return -1. See examples for further clarification.

Definition

Class:: CuttingPaper
Method:: minCuts
Parameters:: String[]
Returns:: int
Method signature:: int minCuts(String[] paper)
(be sure your method is public)

Notes

Two squares of the paper connected by only one vertex are not considered connected. This means you do not need to cut the shared corner. See example 1 for further clarification.
The paper can contain holes and several separated pieces can be described in the input (see example 1 for clarification).
If the ith element of paper contains less than j+1 characters, it means that in row i, there is no paper at any column greater than or equal to j. See example 1 for further clarification.

Constraints

paper will contain between 1 and 50 elements, inclusive.
Each element of paper will contain between 1 and 50 characters, inclusive.
Each character of each element of paper will be a space (' ') or an uppercase letter ('A'-'Z').

Examples

```
{"AABB",
 "AABB",
 "BBDD",
 "BBDD"}
```
```
Returns: 3
```
You can first cut the paper in half vertically, and then cut each of the 2 resulting pieces in half horizontally. Note that if you first cut out a corner (the square containing the A's for instance), you cannot cut out the opposite corner with only one extra cut because the middle point will no longer be surrounded by paper and it will interrupt your second cut.
```
{"  X",
 " XXX A Y",
 "XX XX YYY",
 " XXX B Y",
 "  X"}
```
```
Returns: 0
```
Note that the paper can contain holes. Also note that it is possible to have more than one piece of paper and that corner connected pieces are considered to be already separated.
```
{"AAA",
 "ABA",
 "AAA"}
```
```
Returns: -1
```
There is no way to separate the B from the A's without cutting through the A's (which is not allowed).
```
{"ABBBB",
 "AABBB",
 "AAABB",
 "AAAAB"}
```
```
Returns: 1
```
Note that the cut does not need to be a straight line.

{"AABB",
 "A BB",
 "CCDD",
 "CCDD"}

Returns: 4

Each cut must be done separately.

```
{"BAA",
 "ABA",
 "AAA"}
```
```
Returns: 2
```
Note that you can't go around the inner B and continue the cut because the second time you pass through its upper left corner, it is no longer surrounded by paper and therefore your cut must end.
```
{"BBB CCCC",
 "BAB CD C",
 "BB  CCCC"}
```
```
Returns: 2
```
You can cut the A out with a single cut starting on in its lower-right corner. You can also cut the D out starting in any of its right corners.

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.