forked from keshavnandan/Topcoder
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathDropCoins.txt
106 lines (72 loc) · 2.14 KB
/
DropCoins.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
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 vector <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:vector <string>, int
Returns:int
Method signature:int getMinimum(vector <string> board, int K)
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
0)
{".o.."
,"oooo"
,"..o."}
3
Returns: 2
One of the optimal solutions is to move coins to the right twice.
1)
{".....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)
2)
{"...."
,".oo."
,".oo."
,"...."}
3
Returns: -1
It is impossible to make the number of remaining coins exactly 3.
3)
{"......."
,"..ooo.."
,"ooooooo"
,".oo.oo."
,"oo...oo"}
12
Returns: 4
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.."
,"................."}
58
Returns: 6