CollectAllCoins | Topcoder Archive

Problem Statement

R * C coins are arranged into a grid with R rows and C columns. The coins are numbered in row major order, starting from zero. (That is, top row from left to right has coins 0 to C-1, second row has coins C to 2C-1, and so on.)

Coin 0 is heads up, all other coins are tails up.

You want to remove all coins, one after another. There are two rules:

You can only remove a coin if it's heads up.
Whenever you remove a coin, you must flip all coins that are horizontally or vertically adjacent.

Return a int[] containing the numbers of coins in an order in which they can be removed. Any valid solution will be accepted. If there is no solution, return an empty int[] instead.

Definition

Class:: CollectAllCoins
Method:: collect
Parameters:: int, int
Returns:: int[]
Method signature:: int[] collect(int R, int C)
(be sure your method is public)

Constraints

R will be between 1 and 30, inclusive.
C will be between 1 and 30, inclusive.

Examples

```
3
```
```
3
```
```
Returns: {0, 3, 4, 6, 5, 2, 8, 7, 1 }
```
The nine coins are numbered as follows: 012 345 678 Below we illustrate the example return value by showing the state of the board at the beginning and also after each step. ('H' denotes a coin that's heads, 'T' denotes a coin that's tails, and '.' a coin that has already been removed.) 0: 1: 2: 3: 4: 5: 6: 7: 8: 9: HTT .HT .HT .TT .TT .TH .H. .H. .H. ... TTT HTT .HT ..H ..H ... ... ... ... ... TTT TTT HTT HHT .TT .TH .TH .H. ... ... There are other valid solutions, too.
```
7
```
```
1
```
```
Returns: {0, 1, 2, 3, 4, 5, 6 }
```
This is the only correct answer
```
2
```
```
3
```
```
Returns: {0, 1, 2, 3, 5, 4 }
```
The coins on the board are numbered as follows: 012 345
```
14
```
```
28
```
```
Returns: { }
```

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.