Fake bills
本题没有可用的提交语言。
Description
The bank Monopoly has recently been very worried by the possibility of a robbery, as they don't want to lose their fake bills. To reinforce their security, they have implemented a system of security cameras in front of their vault. Now they are worried that it might have flaws, so they have asked for your help.
The room where the vault is located can be represented as an $n \times n$ grid, where the cell $(1, 1)$ is the entrance, and the vault is in the cell $(n, n)$. There are $m$ cameras in the room, each of them occupying exactly one cell. The cameras can point in $4$ different directions: up, down, left and right. Each camera initially points in one direction, which may be different between cameras. When a camera points in one direction, it covers all the cells in that direction, including the cell in which it is located.
More formally, let the camera be in the cell $(r, c)$, where $r$ represents the row from the top and $c$ the column from the left, then:
- If the camera points up, for all $1 \le i \le r$, the camera covers the cell $(i, c)$.
- If the camera points down, for all $r \le i \le n$, the camera covers the cell $(i, c)$.
- If the camera points left, for all $1 \le j \le c$, the camera covers the cell $(r, j)$.
- If the camera points right, for all $c \le j \le n$, the camera covers the cell $(r, j)$.
If a robber is at a cell covered by a camera, he will be caught.
Additionally, as Monopoly's owners are very paranoic, each second the cameras will rotate $90^\circ$ anticlockwise (i.e. if a camera points down, it will point to the right; if it points to the right, it will point up; and so on). The robbers that try to break into the vault will have to start at cell $(1, 1)$ and reach the cell $(n, n)$ without being seen by the cameras. Each second, robbers can do one of two things:
- Stay at the cell where they are.
- Move to an adjacent cell (i.e. a cell which shares a side with the cell they are in).
Note that the cameras and the robbers move simultaneously, so a robber can move to a cell which is currently covered by a camera as long as it is uncovered on the next second. See the samples section for an example of this.
Your task is to determine if a robber can reach the vault.
The first line contains a single integer $t$, denoting the number of test cases. ($1 \le t \le 100$).
The first line of each test case contains two integers $n$ and $m$, denoting the size of the grid and the number of cameras, respectively. ($1 \le n \le 1000$; $0 \le m \le \max(0, n^2 - 2)$).
Then follow $m$ lines, each of them with two integers $r$ and $c$, representing the row and column of the camera, and a character $d$ which will be one of 'U', 'D', 'L', 'R', representing the initial direction of the camera. ($1 \le r, c \le n$).
It is guaranteed that no two cameras share the same cell, that no cameras initially cover the cell $(1, 1)$, and that there isn't a camera at the cell $(n, n)$.
Additionally, it is guaranteed that the sum of $n$ over all test cases is at most $1000$.
For each test, you should output "YES" if a robber can reach the vault or "NO" if he can't.
Input
The first line contains a single integer $t$, denoting the number of test cases. ($1 \le t \le 100$).
The first line of each test case contains two integers $n$ and $m$, denoting the size of the grid and the number of cameras, respectively. ($1 \le n \le 1000$; $0 \le m \le \max(0, n^2 - 2)$).
Then follow $m$ lines, each of them with two integers $r$ and $c$, representing the row and column of the camera, and a character $d$ which will be one of 'U', 'D', 'L', 'R', representing the initial direction of the camera. ($1 \le r, c \le n$).
It is guaranteed that no two cameras share the same cell, that no cameras initially cover the cell $(1, 1)$, and that there isn't a camera at the cell $(n, n)$.
Additionally, it is guaranteed that the sum of $n$ over all test cases is at most $1000$.
Output
For each test, you should output "YES" if a robber can reach the vault or "NO" if he can't.
3
3 1
2 2 U
3 3
2 2 U
3 2 R
1 3 U
3 2
1 3 U
2 3 U
YES
NO
NO
Note
—
Problem idea: Esomer
Problem preparation: Esomer
Ocurrences: Novice 9