Bear and Random Grid

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Don't miss the "Tests Generation" section. The input is generated in a special way for this problem.
Bear Limak lives in a square grid that consists of N rows and N columns. Each cell is either empty or blocked, denoted with character '.' or '#' respectively. Limak can only visit empty cells and he can't move outside the grid.
Limak wants to impress a girl he likes. He should make a sequence of moves described by a string S of length L. Each character is one of 'R', 'L', 'U', 'D', denoting directions: right, left, up and down respectively.
Depending on the starting cell, making all L moves might be impossible. Limak considers each empty cell as a starting one and wonders how many moves in the sequence he can make, before being forced to stop. For example, if S starts with 'R' but a cell on the right from the starting cell is blocked (or is outside the grid), Limak would do 0 moves.
Your task is to find the number of moves Limak would do from each starting cell, and print the bitwise XOR of those numbers.
Tests Generation
The input in this problem is generated as follows. For each test case we manually chose only three values: two integers L and N and one real value P (0 ≤ P < 1). Each character in S is chosen (generated) uniformly at random from the four allowed characters. Each cell in the grid is blocked with probability P, and empty otherwise. If all cells are blocked, the test case is generated again, so it is guaranteed that at least one cell is empty.
Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains two integers L and N denoting the length of the sequence of moves and the size of the grid.
The second line of a test case contains a string S denoting the sequence of moves.
Next N lines describe the grid. The ith line contains a string of length N denoting the ith row of the grid.
Output
For each test case, output a single line containing one integer — the bitwise XOR of the number of moves made by Limak from each possible starting cell.Constraints
 1 ≤ T ≤ 3
 1 ≤ L ≤ 5000
 1 ≤ N ≤ 1000
 S will contain exactly L characters.
 Each character in S will be one of four: 'R', 'L', 'U', 'D'.
 Each string denoting a row of the grid will contain exactly N characters.
 Each character in the grid will be one of two: '.' or '#'.
 At least one cell will be empty.
 Both the grid and the sequence of moves are generated according to the description above.
 0 ≤ P < 1
Subtasks
 Subtask #1 (15 points) 1 ≤ N ≤ 10
 Subtask #2 (30 points) P = 0, which means that all cells are empty.
 Subtask #3 (30 points) P ≥ 0.1
 Subtask #4 (25 points) original constraints
Example
Input: 2 3 4 DDU #..# #... ...# ..#. 10 4 RLLRDDLUUL .... .#.. ..#. .#.# Output: 2 3
Explanation
Test case 1. We are given the grid of size N = 4, and a sequence of L = 3 moves. For each empty cell of the grid, below you can see the number of moves Limak would make:
# 3 3 # # 3 1 0 1 1 0 # 0 0 # 0
The answer is 3 xor 3 xor 3 xor 1 xor 1 xor 1 = 2.
Test case 2. Again, below you can see the number of moves Limak would make from each cell:
2 4 5 0 0 # 2 0 2 0 # 0 0 # 0 #
Author:  errichto 
Editorial  https://discuss.codechef.com/problems/RNDGRID 
Tags  april17, errichto 
Date Added:  20022017 
Time Limit:  3  5 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 