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  rows and  columns, where the cell in the -th row and the -th column is denoted as . 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 , both  and  are walls; And for all , both  and  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 , it can know the types of five cells: , , ,  and .

The controller accepts a string  consisting of exactly 243 () 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 .

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

 

The controller works as follows. Note that we still assume that the robot is currently in cell , and we denote  as the type of cell .

  1. Calculate ;
  2. Read the -th character in  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  instructions.

Input

There are multiple test cases. The first line of the input contains an integer , indicating the number of test cases. For each test case:

The first line contains two integers ,  (, ), indicating the size of the room.

The second line contains three integers ,  and  (, , ), where  and  indicates that the robot starts from cell , and  indicates the number of instructions the robot executes.

The third line contains a string  (), indicating the program fed into the controller.

For the following  lines, the -th line contains a string  () consisting of '0', '1' and '2', where the -th character of  indicates the type of cell .

It's guaranteed that

  • For all , both  and  are walls; And for all , both  and  are walls;
  • Cell  is not a wall;
  • The sum of  of all test cases will not exceed .

 

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

       相信很多人都到的是用vis数组标记来寻找循环，一旦找到循环就跳出，输出数量就好，因为N*M<=2000所以循环次数绝对不大，但是莫名奇妙的一个个wa掉（我其实就是）。

       其实我们没有想到的就是只用一个标记来看是否进入循环是错误的。。。最大的错误原因就在那个‘P’指令处理type = 2的房间上：：：：一旦处理完毕，那么这个房间的type会发生变化-！！这样最大的问题就是会毁坏原先本循环的循环节，大家想一想~~。所以最重要的是每次‘P’指令typt  = 2的房间，都应该重新开始一个循环节的标记。最不好的方法就是每次都memset一次vis数组，太浪费时间了。我用的是cnt来表示当前循环节，每次处理（‘P’指令typt  = 2的房间）后cnt++，进行新的循环并查询就好了。

 

     后期补充(万能的群友发的)：

 

 

 

#include<bits/stdc++.h>
using namespace std;
int vis[700][700];char mp[700][700];
int main() {
	int te;
	ios::sync_with_stdio(0);
	cin >> te; 
	while (te--) {
		int n, m; cin >> n >> m;
		int stx, sty; 
		long long k;
		cin >> stx >> sty >> k;
		string t;
		cin >> t;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				cin >> mp[i][j];
			}
		}
		int cnt = 1, x = stx, y = sty, su = 0;
		memset(vis, 0, sizeof vis);
		while (k--) {
			int go = 3 * 3 * 3 * 3 * (mp[x][y] - '0') + 3 * 3 * 3 * (mp[x - 1][y] - '0') +
				3 * 3 * (mp[x + 1][y] - '0') + 3 * (mp[x][y - 1] - '0') + (mp[x][y + 1] - '0');
			char g = t[go];
			if (g == 'U') {
				if (mp[x - 1][y] != '1')x--;
				if (vis[x][y] == cnt) {
					break;
				}
				vis[x][y] = cnt;
			}
			else if (g == 'D') {
				if (mp[x + 1][y] != '1')x++;
				if (vis[x][y] == cnt) {
					break;
				}
				vis[x][y] = cnt;
			}
			else if (g == 'L') {
				if (mp[x][y - 1] != '1')y--;
				if (vis[x][y] == cnt) {
					break;
				}
				vis[x][y] = cnt; 
			}
			else if (g == 'R') {
				if (mp[x][y + 1] != '1')y++;
				if (vis[x][y] == cnt) {
					break;
				}
				vis[x][y] = cnt;
			}
			else if (g == 'P') {
				if (mp[x][y] == '2') {
					mp[x][y] = '0'; 
					su++;cnt++;//cnt++代表进入新的循环。
				}
				else {
					if (vis[x][y] == cnt) {
						break;
					}
				}		
				vis[x][y] = cnt;
			}
			else {
				if (vis[x][y] == cnt) {
					break;
				}
				vis[x][y] = cnt;
			}
		}
		cout << su << endl;
	}
	return 0;
}