CF-GYM-101608-E

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 {cell1, cell2, cell3, cell2, cell3} 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.

Input

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 sr, sc, the row and the column of the starting cell (a free cell). Followed by a space then a single uppercase letter sdir, 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.

Output

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

Example

Input
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
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

Output

1
2
3
7
0
1

题意：

机器人在地图中=，并输入了一堆指令
1.R 顺时针旋转
2.F x向前走x步，若无法向前走（走出地图或有障碍）则先顺时针旋转知道能走，再x步
输入了一些指令但是有很多冗余，化简这些指令，使得机器人能走过的每个点都按顺序依次走到，输出化简后命令数

解：

模拟即可

  1. 按照输入的命令记录走过了哪些点，如果没有移动特判输出0
  2. 假设只有F x命令，往前走一步，若离开了路径，则需要加一个R命令，除了一开始是在F之前加R，之后每一个都是加R…F(详见代码）
  3. 得到的步数即为所求
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
#include<iostream>
#include<stdio.h>
#include<queue>
#include<string>
#include<string.h>
using namespace std;
char mp[510][510];
int dir[4][2] = { { -1,0 },{ 0,1 },{ 1,0 },{ 0,-1 } };
int n, m, q, r, c;
struct point//构造点对象
{
	int x, y;
	point() {}
	point(int x, int y)
	{
		this->x = x;
		this->y = y;
	}
	bool judge()
	{
		if (x > 0 && x <= n)
			if (y > 0 && y <= m)
				if (mp[x][y] == '.')
					return true;
		return false;
	}
	bool operator==(const point&p)const
	{
		return x == p.x&&y == p.y;
	}
};
queue<point>que;
struct robot//构造机器人对象
{
	int x, y, d;//坐标（x，y）方向0上 1下 2左 3右
	robot() {}
	robot(int x, int y, char d)//构造函数
	{
		this->x = x;
		this->y = y;
		switch (d)
		{
		case 'U':this->d = 0; break;
		case 'D':this->d = 2; break;
		case 'L':this->d = 3; break;
		case 'R': this->d = 1; break;
		default:break;
		}
	}
	void rotate()//旋转
	{
		d++;
		d %= 4;
	}
	void go_straight()//先前走，包含了旋转
	{
		int time = 0;
		while (!point(x + dir[d][0], y + dir[d][1]).judge())
		{
			d++;
			d %= 4;
			time++;
			if (time > 5)
			{
				break;
			}
		}
		if (point(x + dir[d][0], y + dir[d][1]).judge())
		{
			x = x + dir[d][0]; y = y + dir[d][1];
		}
	}
};
int main()
{
	freopen("reduce.in", "r", stdin);
	int T;
	scanf("%d", &T);
	while (T--)
	{
		while (que.size())
		{
			que.pop();
		}
		memset(mp, 0, sizeof(mp));
		char init_dir[3];
		scanf("%d%d%d%d%d", &n, &m, &q, &r, &c);
		scanf("%s", init_dir);
		for (int i = 1; i <= n; i++)
		{
			scanf("%s", mp[i] + 1);
		}
		robot first = robot(r, c, init_dir[0]);
		for (int I = 1; I <= q; I++)
		{
			char order[3];
			scanf("%s", order);
			if (order[0] == 'R')
			{
				first.rotate();
			}
			else
			{
				int x;
				scanf("%d", &x);
				while (x--)
				{
					first.go_straight();
					que.push(point(first.x, first.y));
				}
			}
		}
		robot sec = robot(r, c, init_dir[0]);
		robot temp;
		int ans = 1;
		int flag = 0;
		if (que.size() == 0)
		{
			ans = 0;
			printf("0\n"); continue;
		}
		while (!que.empty())
		{
			temp = sec;
			temp.go_straight();
			if (!(point(temp.x, temp.y) == que.front()))
			{
				while (!(point(temp.x, temp.y) == que.front()))
				{
					sec.rotate();
					ans++;
					temp = sec;
					temp.go_straight();
				}
				if (flag != 0)
					ans++;
			}
			else
			{
				flag = 1;
				sec = temp;
				que.pop();
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}