DropCoins | Topcoder Archive

Problem Statement

There is a rectangle divided into 1x1 cells. Each cell is either empty or it contains a single coin.

You can apply the following operation repeatedly.

First, choose one of the directions: up, down, left, or right.
Then, move all coins in the chosen direction by exactly 1 cell. If this would cause a coin to move out of the rectangle, the coin drops out from the rectangle and disappears.

Your objective in this problem is to apply the operations so that the number of coins remaining on the rectangle becomes exactly K.

You are given the int K and a String[] board that describes the initial state of the rectangle. More precisely, character j of element i of board is 'o' if i-th row of j-th column of the rectangle contains a coin, and it is '.' otherwise.

Return the minimum number of operations you have to perform. If the objective is impossible, return -1.

Definition

Class:: DropCoins
Method:: getMinimum
Parameters:: String[], int
Returns:: int
Method signature:: int getMinimum(String[] board, int K)
(be sure your method is public)

Constraints

board will contain between 1 and 30 elements, inclusive.
Each element of board will contain between 1 and 30 characters, inclusive.
All elements of board will contain the same number of characters.
Each character in each element of board will be either '.' or 'o'.
K will be between 1 and 900, inclusive.

Examples

```
{".o.."
,"oooo"
,"..o."}
```
```
3
```
```
Returns: 2
```
One of the optimal solutions is to move coins to the right twice.
```
{".....o"
,"......"
,"oooooo"
,"oooooo"
,"......"
,"o....."}
```
```
12
```
```
Returns: 3
```
One of the optimal solutions: move coins up (1 coin drops, 13 remain) move coins down move coins down again (1 coin drops, 12 remain)
```
{"...."
,".oo."
,".oo."
,"...."}
```
```
3
```
```
Returns: -1
```
It is impossible to make the number of remaining coins exactly 3.

{"......."
,"..ooo.."
,"ooooooo"
,".oo.oo."
,"oo...oo"}

Returns: 4

{"................."
,".ooooooo...oooo.."
,".ooooooo..oooooo."
,".oo.......oo..oo."
,".oo.......oo..oo."
,".ooooo.....oooo.."
,".ooooooo...oooo.."
,".....ooo..oo..oo."
,"......oo..oo..oo."
,".ooooooo..oooooo."
,".oooooo....oooo.."
,"................."}

Returns: 6

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.