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.
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.
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 i-th line contains a string of length N denoting the i-th row of the grid.
OutputFor 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.
- 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
- 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
Input: 2 3 4 DDU #..# #... ...# ..#. 10 4 RLLRDDLUUL .... .#.. ..#. .#.# Output: 2 3
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 #
|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|
Fetching successful submissions
If you are still having problems, see a sample solution here.