406364: GYM102391 C Cleaning

Minje operates a game arcade. One of the games is situated in a grid of size $$$N \times M$$$. In each cell, one of the four characters L, R, U, D is written. This denotes the left/right/up/down direction, respectively. A player can freely move inside the grid, but he can NOT move toward the direction written in his cell, or outside of the grid.

Minje cleans the grid after the player enters and leaves the grid. However, cleaning all $$$N \times M$$$ cells is tiring. So Minje wants to only clean the cell which can be possibly visited by the player.

There are $$$Q$$$ players who participated in the game. Minje remembers the first cell and the last cell that each player had stood during the game. These cells are not necessarily at the corner or edge. Please calculate the number of cells which Minje should clean. Every game is independent and does not affect other games' results.

In the first line, three integers $$$N, M, Q$$$ are given, denoting the size of the grid and the number of players, respectively. ($$$1 \le N, M \le 1\,000$$$, $$$1 \le Q \le 300\,000$$$)

In the next $$$N$$$ lines, strings of size $$$M$$$ are given, denoting the character written in each grid cell. Every character is one of these four letters: L, R, U, D.

In the next $$$Q$$$ lines, four integers $$$x_1, y_1, x_2, y_2$$$ are given. This denotes that the player started the game in cell $$$(x_1, y_1)$$$, and ended the game in cell $$$(x_2, y_2)$$$. ($$$1 \le x_1, x_2 \le N, 1 \le y_1, y_2 \le M$$$)

In each of the $$$Q$$$ lines, print the single integer denoting the answer for the query, in the order of the input. The answer to the query is:

• 0 if it's impossible to move from cell $$$(x_1, y_1)$$$ to cell $$$(x_2, y_2)$$$.
• Otherwise, print the number of cells that Minje should clean.

5 5 5
DDDDD
RDDDL
RRDLL
RUUUL
UUUUU
1 1 5 5
2 2 5 5
3 3 5 5
4 4 5 5
5 5 5 5

0
14
20
14
5