blob: 9dbaa65ebf634b85c932e738ce4c84578e8f686d (
plain)
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
|
// 838. Push Dominoes
#include "leetcode.h"
/*
* there are 'n' dominoes in a line, and we place each domino vertically
* upright. in the beginning, we simultaneously push some of the dominoes either
* to the left or to the right. after each second, each domino that is falling
* to the left pushes the adjacent domino on the left. similarly, the dominoes
* falling to the right push their adjacent dominoes standing on the right. when
* a vertical domino has dominoes falling on it from both sides, it stays still
* due to the balance of the forces. for the purpose of this question, we will
* consider that a falling domino expends no additional force to a falling or
* already fallen domino.
*/
char *pushDominoes(char *dominoes) {
int n = strlen(dominoes), right = -1;
for (int i = 0; i < n; ++i) {
if (dominoes[i] == 'L') {
if (right == -1) {
for (int j = i - 1; j >= 0 && dominoes[j] == '.'; --j)
dominoes[j] = 'L';
} else {
for (int j = right + 1, k = i - 1; j < k; ++j, --k) {
dominoes[j] = 'R';
dominoes[k] = 'L';
}
right = -1;
}
} else if (dominoes[i] == 'R') {
if (right != -1)
for (int j = right + 1; j < i; ++j)
dominoes[j] = 'R';
right = i;
}
}
if (right != -1)
for (int i = right + 1; i < n; ++i)
dominoes[i] = 'R';
return dominoes;
}
int main() {
char *d1 = "RR.L", *d2 = ".L.R...LR..L..";
printf("%s\n", pushDominoes(d1)); // expect: RR.L
printf("%s\n", pushDominoes(d2)); // expect: .L.R...LR..L..
}
|