404681: GYM101608 E Robot I - Instruction Reduction

You built a new robot that moves over r × c grid. The rows of the grid are numbered from 1 to r from top to bottom, and the columns are numbered from 1 to c from left to right. The grid contains free and blocked cells, and the robot can only move over the free cells. All cells on the border of the grid are blocked. The robot reads the movement instructions from a file on its SD card and starts performing them.

It performs only two types of movement instructions:

• Rotate 90 degrees clockwise. The time taken in this instruction is negligible (zero time).
• Move x cells forward, where x is a positive integer. If the next cell in the current direction is blocked, the robot rotates 90 degrees clockwise and tries again. This instruction takes x seconds to be completed.

When you tried to upload the new instruction file to the SD card, you received an out-of-memory error. You want to rewrite the instructions in such a way that the robot will visit the same cells in the same order. For example, if by performing the instruction file, the robot visits {cell₁, cell₂, cell₃, cell₂, cell₃} in this order, the new instructions should make the robot visit the same cells in the same order.

Given the initial position and direction, the grid, and the original instructions, what is the minimum number of instructions needed to visit the same cells in the same order? Note that you cannot change the initial position and direction.

The first line of input contains a single integer T (1 ≤ T ≤ 128), the number of test cases.

The first line of each test case contains three integer r, c, and q (3 ≤ r, c ≤ 500) (1 ≤ q ≤ 1000), the number of rows and columns of the grid, and the number of instructions in the file, respectively.

The second line of each test case contains two integers s_r, s_c, the row and the column of the starting cell (a free cell). Followed by a space then a single uppercase letter s_dir, which is the initial direction of the robot, it can only be one of the four letters {'U', 'D', 'L', 'R'}, each letter represents one of the four directions: up, down, left, and right, respectively.

Each of the following r lines contain c characters that are either ‘.’ (a free cell), or ‘#’ (a blocked cell). It is guaranteed that each free cell has at least one adjacent free cell, and all cells on the border of the grid are blocked.

Each of the following q lines contains an instruction, each instruction will be in one of two formats:

• ‘R’ , that represents the first type of movement "Rotate".
• ‘F’ x, that represents the second type of movement "Move x" (1 ≤ x ≤ 1000).

Note that the robot performs the given instructions in the given order.

For each test case, print the minimum number of instructions needed to visit the same cells in the same order.

3
6 10 12
2 9 U
##########
#........#
#.#.....##
#........#
#...#....#
##########
R
R
R
F 3
F 4
R
R
R
F 2
R
R
F 2
4 4 2
2 2 R
####
#..#
#..#
####
R
R
4 4 3
3 2 R
####
#.##
#.##
####
F 1000
R
F 1000

7
0
1

In the first test case, the following 7 instructions will visit the same cells as the given instructions and in the same order: F 7, R, R, R, F 2, R, F 2.

In the second test case, there's no need for any instruction, as the robot didn't visit any cell.