
ZOJ Problem Set  4092
Tired of tidying up his room, BaoBao decides to invent a robot cleaner to help him do the cleaning. Let's consider BaoBao's room as a grid with $n$ rows and $m$ columns, where the cell in the $i$th row and the $j$th column is denoted as $(i, j)$. Each cell belongs to one of the following three types:
As we know, rooms are surrounded by walls. So it's guaranteed that for all $1 \le i \le n$, both $(i, 1)$ and $(i, m)$ are walls; And for all $1 \le j \le m$, both $(1, j)$ and $(n, j)$ are walls. After days of hard work, BaoBao successfully creates his very first robot cleaner. The robot is equipped with five sensors, four wheels, a robot arm, and a very simple controller. The sensors can detect the type of the cell the robot is currently in, as well as the types of the four neighboring cells. That is to say, if the robot is in cell $(i, j)$, it can know the types of five cells: $(i, j)$, $(i1, j)$, $(i+1, j)$, $(i, j1)$ and $(i, j+1)$. The controller accepts a string $s$ consisting of exactly 243 ($243 = 3^5$) characters as the program, where each character represents an instruction, and controls the robot according to the program and the values returned from the sensors. We now list the valid instructions below, and we assume that the robot is currently in cell $(i, j)$.
The controller works as follows. Note that we still assume that the robot is currently in cell $(i, j)$, and we denote $t(i, j)$ as the type of cell $(i, j)$.
Given the map of BaoBao's room, the program string and the starting position of the robot, please calculate the number of pieces of litter the robot can pick up after executing $k$ instructions. InputThere are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case: The first line contains two integers $n$, $m$ ($n, m \ge 3$, $n \times m \le 2000$), indicating the size of the room. The second line contains three integers $a$, $b$ and $k$ ($1 < a < n$, $1 < b < m$, $1 \le k \le 10^{18}$), where $a$ and $b$ indicates that the robot starts from cell $(a, b)$, and $k$ indicates the number of instructions the robot executes. The third line contains a string $s$ ($s = 243 = 3^5$), indicating the program fed into the controller. For the following $n$ lines, the $i$th line contains a string $r_i$ ($r_i = m$) consisting of '0', '1' and '2', where the $j$th character of $r_i$ indicates the type of cell $(i, j)$. It's guaranteed that
OutputFor each test case output one line containing one integer, indicating the number of pieces of litter the robot can pick up after executing $k$ instructions. Sample Input2 5 5 2 4 6 RUPIRPIUDDLRUDRURLIIURDLPRDLDIRLIDPPRRRLLULPRPUPPDPRIUIUDLULIRIDIRPUPPIRRLRLULUPLRIIRLPRLLRLDLLPDRUUDLDPRRPLLPPUIUUPPLUIILLDRIDILDRRUPLPPLPDLDPDDUPIPPUIILIPLUPLURRPIIDDPPIUPRPRIRDRPPIUIRDUUUPPPDIIRPURIUIUIPLRILLDPPPURPPRRPDPRRLUDUDUDUPRLIUIRLR 11111 12021 10101 12021 11111 4 5 2 2 1000000000000000000 IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII 11111 10021 11211 11111 Sample Output2 0 Author: WENG, Caizhi Source: The 19th Zhejiang University Programming Contest Sponsored by TuSimple 