TheKingsArmyDiv1 | Topcoder Archive

Problem Statement

The King of Byteland has an army. The army consists of 2N soldiers. The King has arranged the soldiers into 2 rows by N columns. Two soldiers are neighbors if they are located next to each other in a row or in a column.

Currently, some of the soldiers are happy and some are sad. You are given the current states of all soldiers in a String[] state. For each i and j, state[i][j] is 'H' if soldier in row i, column j is happy, or 'S' if that soldier is sad. (All indices are 0-based.)

The King knows that a happy army is a strong army, therefore he wants all his soldiers to be happy. The soldiers can talk to other soldiers. Whenever soldier X talks to soldier Y, soldier Y changes his state to the state of soldier X. For example, if X is currently sad, Y becomes sad as well. The state of soldier X does not change when X talks to Y.

You can now give some soldiers orders to talk to other soldiers. There are three types of valid orders:

Choose a single soldier and call him X. Choose a single neighbor of X and call him Y. X will talk to Y.
Choose any contiguous group of soldiers in one of the rows. Each of these soldiers will talk to their neighbor in the other row.
Choose any column A. Choose any column B adjacent to column A. Each soldier in column A will talk to their neighbor in column B.

You are given the String[] state. Return the smallest non-negative integer X such that there is a sequence of X valid orders such that after the orders are executed, one after another, all the soldiers will be happy. If there is no such sequence of orders, return -1 instead.

Definition

Class:: TheKingsArmyDiv1
Method:: getNumber
Parameters:: String[]
Returns:: int
Method signature:: int getNumber(String[] state)
(be sure your method is public)

Constraints

N will be between 1 and 200, inclusive.
state will contain exactly 2 elements.
Each element of state will contain exactly N characters.
Each element of state will consist of characters 'H' and 'S'.

Examples

```
{"HSH", 
 "SHS"}
```
```
Returns: 2
```
Here is one optimal solution: First, give an order of the first type, choosing the soldier in row 1, column 1 (0-based indices) as X and the soldier in row 0, column 1 as Y. Next, give an order of the second type, choosing the entire row 0.
```
{"HH", 
 "HH"}
```
```
Returns: 0
```
All soldiers are already happy, hence the answer is 0.
```
{"HHHHH", 
 "HSHSH"}
```
```
Returns: 1
```
One optimal solution is to give an order of the second type, choosing soldiers in columns 1 through 3 in row 0.
```
{"S", 
 "S"}
```
```
Returns: -1
```
It is impossible to achieve the goal in this case.

{"HSHHSHSHSHHHSHSHSH", 
 "SSSSHSSHSHSHHSSSSH"}

Returns: 8

```
{"HS",
 "HS"}
```
```
Returns: 1
```

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.