P10498 Stone Game

The stone game is played on a grid with $n$ rows and $m$ columns. Each cell corresponds to an operation sequence. There are at most $10$ kinds of operation sequences, denoted by the digits $0 \sim 9$. An operation sequence is a string of length at most $6$ that repeats in a cycle, executing one character per second. Every second, all cells execute the next character in their own operation sequence at the same time. Each character in a sequence is one of the following: 1. A digit $0 \sim 9$: move $0 \sim 9$ stones into this cell. 2. `NWSE`: push all stones in this cell to an adjacent cell. `N` means up, `W` means left, `S` means down, and `E` means right. If the operation is invalid (i.e., the stones would be pushed out of the grid), then the stones disappear. 3. `D`: remove all stones from this cell. You are given the string for each operation sequence, and for each cell in the grid, which operation sequence it uses. Find, after $t$ seconds, how many stones are in the cell that has the most stones. At the start of the game, the grid is empty.

The first line contains $4$ integers $n, m, t, act$. The next $n$ lines each contain $m$ characters, indicating the operation sequence used by each cell. The last $act$ lines each contain one string, describing each operation sequence starting from $0$.

Output one integer: after $t$ seconds, the maximum number of stones among all cells.

For all testdata, $1 \le m, n \le 8$, $1 \le t \le 10^8$, $1 \le act \le 10$. Translated by ChatGPT 5