Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 4092
Robot Cleaner I

Time Limit: 1 Second      Memory Limit: 65536 KB

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:

  • Type 0: This cell is empty;
  • Type 1: This cell is a wall;
  • Type 2: This cell contains a piece of litter.

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)$, $(i-1, j)$, $(i+1, j)$, $(i, j-1)$ 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)$.

  • U: If $(i-1, j)$ is not a wall, move the robot from $(i, j)$ to $(i-1, j)$. Otherwise do nothing;
  • D: If $(i+1, j)$ is not a wall, move the robot from $(i, j)$ to $(i+1, j)$. Otherwise do nothing;
  • L: If $(i, j-1)$ is not a wall, move the robot from $(i, j)$ to $(i, j-1)$. Otherwise do nothing;
  • R: If $(i, j+1)$ is not a wall, move the robot from $(i, j)$ to $(i, j+1)$. Otherwise do nothing;
  • P: If $(i, j)$ contains a piece of litter, the robot will pick up the litter. Otherwise do nothing. Note that after picking up the litter, $(i, j)$ becomes an empty cell;
  • I: Do nothing.

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)$.

  1. Calculate $x = 3^4 \times t(i, j) + 3^3 \times t(i-1, j) + 3^2 \times t(i+1, j) + 3 \times t(i, j-1) + t(i, j+1)$;
  2. Read the $(x + 1)$-th character in $s$ as the instruction and execute it. After that, go back to step 1.

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.

Input

There 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

  • 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;
  • Cell $(a, b)$ is not a wall;
  • The sum of $n \times m$ of all test cases will not exceed $2 \times 10^4$.

Output

For 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 Input

2
5 5
2 4 6
RUPIRPIUDDLRUDRURLIIURDLPRDLDIRLIDPPRRRLLULPRPUPPDPRIUIUDLULIRIDIRPUPPIRRLRLULUPLRIIRLPRLLRLDLLPDRUUDLDPRRPLLPPUIUUPPLUIILLDRIDILDRRUPLPPLPDLDPDDUPIPPUIILIPLUPLURRPIIDDPPIUPRPRIRDRPPIUIRDUUUPPPDIIRPURIUIUIPLRILLDPPPURPPRRPDPRRLUDUDUDUPRLIUIRLR
11111
12021
10101
12021
11111
4 5
2 2 1000000000000000000
IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII
11111
10021
11211
11111

Sample Output

2
0

Author: WENG, Caizhi
Source: The 19th Zhejiang University Programming Contest Sponsored by TuSimple
Submit    Status