P4621 [COCI 2012/2013 #6] BAKTERIJE

There is a rectangular area with $N$ rows and $M$ columns. Rows are numbered from $1$ to $N$ from top to bottom, and columns are numbered from $1$ to $M$ from left to right. There are $K$ bacteria placed in these cells. Each bacterium has its own direction and movement rules. The rules are as follows: it reads the digit $X$ in its current cell, then turns clockwise by $90^{\circ}$ exactly $X$ times. If it is facing the boundary of the rectangle, it turns $180^{\circ}$. Finally, it moves into the cell it is facing. We place a trap in one cell. When all bacteria enter the trap at the same time, the trap is activated, and the bacteria will be destroyed within one second. Given all information, determine when all bacteria are destroyed.

The first line contains three positive integers $N, M, K$. The next line contains two integers $x, y$, meaning there is a trap at row $x$, column $y$. Then each bacterium is described in order: - First, one line contains two integers $X, Y$ and one letter $C$, representing its row and column coordinates and its direction. `U` means up, `D` means down, `L` means left, and `R` means right. - Next is a matrix giving the value $X$ for this bacterium in every cell, with $0\leq X\leq 9$.

Output one integer on one line: the last time when the bacteria are killed. If it is impossible to destroy all of them, output $-1$.

Constraints: $3\leq N\leq 50$, $3\leq M \leq 50$, $1\leq K\leq 5$. Translated by ChatGPT 5