题目描述
Problem Description
A rectangular area of $N$ rows and $M$ columns, where rows are numbered from 1 to $N$ from top to bottom and columns are numbered from 1 to $M$ from left to right, contains $K$ bacteria, each with its own direction and movement rules. The rules are as follows: read the number $X$ in the cell, rotate $90^{\circ}$ clockwise $X$ times, and if it faces the boundary of the rectangle, rotate $180^{\circ}$ instead, then move into the cell it is facing. A trap is placed in a certain cell, and it activates when all bacteria enter it simultaneously, destroying the bacteria within one second.
Given all the information, determine when all the bacteria are destroyed.
Input Format
The first line contains three positive integers $N, M, K$.
The next line contains two numbers $x, y$ indicating the trap is located at row $x$ and column $y$.
The following lines describe each bacterium:
- The first line contains two numbers $X, Y$ and a letter $C$, representing the row and column coordinates and its direction, where U means up, D means down, L means left, and R means right.
- The next lines form a matrix representing the number $X$ for each cell, where $0 \leq X \leq 9$.
Output Format
A single line containing a number representing the last time the bacteria are killed, or $-1$ if they cannot all be destroyed.
Sample Input and Output
Sample Input #1
3 3 1
2 2
1 1 R
010
000
000
Sample Output #1
3
Sample Input #2
3 4 2
2 2
3 4 R
2327
6009
2112
3 2 R
1310
2101
1301
Sample Output #2
8
Sample Input #3
4 4 3
4 3
1 1 U
1001
0240
3322
2327
1 3 L
9521
2390
3020
2421
2 2 D
3397
2013
1102
7302
Sample Output #3
296
Notes
$3 \leq N \leq 50$, $3 \leq M \leq 50$, $1 \leq K \leq 5$.
输入格式
见题面 Input 部分
输出格式
见题面 Output 部分