96 - ZOJ Monthly, September 2010 - G
The board of marble game can be represented by a two-dimention array which has n rows and m columns. There are act different operation sequences in total. Each grid is assigned a number from 0 to act - 1, corresponding to different operation sequences.
The length of operation sequence is no more than 6. And all of the sequence are executed repeatedly. For example, if the sequence is "1ED1D", it represents "1ED1D1ED1D1ED1D..." in fact. The sequence includes three types of operations:
All sequences operate simultaneously while the first operation starts at 1 second. There are no marbles at 0-th second, and marbles moved outside of the board will disappear.
There are multiple cases. For each test case, the first line contains four integers n, m, t, act. The following n lines, each line contains m digits, indicate the corresponding operation sequence of the grid. Last act lines, each line contains a string of characters, indicate the details of every operation sequence. 1 ≤ n, m ≤ 15, 1 ≤ act ≤ 10, 1 ≤ t ≤ 109.
For each case, output one integer number in a single line.
1 6 10 3 011112 1E E 0
The sample input functions as a conveyor belt. On the left, the device of type 0 alternately grabs one marble and pushes it east. The devices of type 1 move the marble along to the east until they reach the device of type 2, which accumulates the marbles. After 10 cycles, 5 marbles have been brought up. 2 are still on the "conveyor belt", and 3 are on the square at the east end.
Author: HE, Ningxu
Contest: ZOJ Monthly, September 2010