CollectAllCoins
SRM 771 · 2019-11-26 · by misof
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
Constraints
- R will be between 1 and 30, inclusive.
- C will be between 1 and 30, inclusive.
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: { }
1
1
Returns: {0 }
Submissions are judged against all 27 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class CollectAllCoins with a public method vector<int> collect(int R, int C) · 27 test cases · 2 s / 256 MB per case