All submissions for this problem are available.
Ravi is bored in his chemistry class. He's playing with intelligent bacteria. He has
arranged his K bacteria on a rectangular board divided in N rows, labelled with numbers from 1 to N
starting from the top, and M columns, labelled with numbers from 1 to M starting from the left.
Each bacterium begins its adventure in a certain cell, facing one of the four neighbouring cells, and
carries out the following actions every second:
1. Reads the number X dedicated to that bacterium in the current cell.
2. Turns 90 degrees clockwise, X times.
3. If it is facing a cell outside the board, it turns 180 degrees.
4. Finally, it moves to the cell that it is facing.
Ravi has placed a trap in one cell. The trap will activate and kill the bacteria as soon as they all step on
that cell in the same second.
Since Ravi only has two hours of chemistry class today, help him determine how long the game will
last, in seconds.
The first line of input contains the positive integers N (3 ≤ N ≤ 50), M (3 ≤ M ≤ 50), and K (1 ≤ K ≤
The second line of input contains the positive integers X and Y, the row and column where Ravi has
placed the trap.
The remainder of the input consists of bacteria descriptions, for each bacterium i from 1 to K:
- two positive integers Xi,Yi
– the row and column of the starting cell of bacterium i, and the character
Ci representing the starting direction that the bacterium is facing (U – up, R – right, D – down, L –
- N by M matrix of digits between 0 and 9, inclusive; the digit in row x and column y represents the
number in cell (x, y) dedicated to bacterium i.
The first and only line of output must contain the total duration of Ravi's game, in seconds. If the
game will never end, output -1.
Input: 3 3 1 2 2 1 1 R 010 000 000 Output: 3 Input: 3 4 2 2 2 3 4 R 2327 6009 2112 3 2 R 1310 2101 1301 Output: 8
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.