Pikulice

Interview

Time limit1sMemory limit1024 MB

Summary

Find the minimum number of slide and jump moves that turn a row of red and blue marbles with one empty stand into all reds, then the empty stand, then all blues.

Level: Medium5 of 10
Topics: BFS, Graph, Simulation
Solved: No attempts yet

Subproblem

Marin has $N+1$ stands in a row. Exactly one stand is empty, and each of the other stands holds one red or blue marble. Marin moves marbles in one of two ways:

Slide a marble next to the empty stand into the empty stand. The stand the marble left becomes empty.
Jump a marble $A$ over an adjacent marble $B$ , provided $A$ and $B$ are different colors and the empty stand is adjacent to $B$ . $A$ lands on that empty stand, and the stand $A$ left becomes empty.

Each move takes one second.

One evening, Stjepan visited and said that the marbles must first all be red, then the empty stand, then all blue. Marin rearranged his marbles into that order as fast as he could. How many seconds did it take?

Examples3

Example 1
Input
```
2
PCX
```
Expected output
```
2
```
Example 2
Input
```
4
CCXPP
```
Expected output
```
0
```
Example 3
Input
```
4
XCPCP
```
Expected output
```
3
```