Programming Problem #11
"Cellular Networks"

A cellular network consists of a rectangular array of cells. Each cell can receive one or more binary signals from its neighbors and can send a signal to some of its neighbors. All of the cells in a network operate concurrently. Although they are very simple, cellular networks can express very complex behavior. For this problem you will write a program to simulate a cellular network.

The input consists of one or more network descriptions. Each description begins with a header line containing three integers R, C and T and a binary character string S, all separated by a single blank space. The values R and C define the number of rows and columns in the network (1 <= R,C <= 20), T is the number of time units to run the network, and S is a sequence of binary signals of length N, where 1 <= N <= T. Following the header line are R lines of C characters each, describing each cell in the network. Each character will be either a blank space or one of the following characters that indicates the direction(s) in which the cell propagates a signal: <=left, >=right, ^=up, v=down, -=both left and right, |=both up and down, \=both up and right, /=both down and right. Blank cells do not propagate their signal, and signals propagated out of the network are discarded. A cell propagates the logical (inclusive) "or" of its input signals to the indicated neighbors.

For each network in the input, output one line containing a binary string of length T representing the signal at the lower-right cell at the end of each time unit. Initially the signal at all cells is 0 except for the upper-left corner; during the first N time units the only input signal for this cell is the corresponding character in the string S, and afterwards this cell receives input normally. During one time unit, all cells simultaneously send their current signal to the correct neighbors, then they all simultaneously compute the signal for the next time unit as the "or" of the signals they just received.

Input must be read from the file "prob11.in", and output must be written to the file "prob11.out". All output to the screen will be ignored.

Example Input

<BOF>
2 2 5 101
>v
><
2 2 10 1
>v
^<
<EOF>

Example Output

00101
0010001000
A version of this problem originally appeared in the 1986 North Central Regionals.

Dr. Eric Shade