箭头谜题Ⅰ
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

本题与 箭头谜题Ⅱ 在题面描述和任务要求均有不同，我们建议您重新阅读题面。
enar 发现了一个由特殊符号组成的 n \cdot m 大小的迷宫矩阵。矩阵的每个格子包含一个方向地板：\texttt{U}(上)，\texttt{D}(下)，\texttt{L}(左) 或 \texttt{R}(右)。
enar 从矩阵的左上角 (1,1) 出发，想要到达右下角 (n,m)。移动规则如下：
1. 当位于某个位置时，必须按照该位置地板上的方向字符移动：
  • \texttt{U}：向上移动一格，即从 (x, y) 移动至 (x - 1, y) 。
  • \texttt{D}：向下移动一格，即从 (x, y) 移动至 (x + 1, y) 。
  • \texttt{L}：向左移动一格，即从 (x, y) 移动至 (x, y - 1) 。
  • \texttt{R}：向右移动一格，即从 (x, y) 移动至 (x, y + 1) 。
2. 若移动后会超出边界，则此次移动无效。
enar 可以使用最多 k 次魔法，每次使用魔法可以选择任意一个格子并改变其中的方向字符（可以改为 \texttt{U}/\texttt{D}/\texttt{L}/\texttt{R} 中的任意一种）。
请判断 enar 能否在使用至多 k 次魔法的情况下到达目标位置（只要经过目标位置即可）。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数 T\left(1\leq T\leq 10\right) 代表数据组数，每组测试数据描述如下：
  第一行，输入三个整数 n ， m 和 k（1 \leq n, m \leq 10^6，0 \le k \le n + m - 1），分别表示矩阵的行数和列数以及可用魔法的次数。
  接下来 n 行，每行输入 m 个字符（保证只含有 \texttt{U}，\texttt{D}，\texttt{L}，\texttt{R}），表示迷宫矩阵。
保证单个测试文件的 n \cdot m 的总和不超过 10^6。

输出描述:

T 行，对于每个测试数据，如果 enar 能到达目标位置，则输出 "YES"（不带引号），否则输出 "NO"（不带引号）。
示例1

输入

复制 
1
3 3 2
RLD
UDU
UUL

输出

复制 
YES

说明

样例输入矩阵如下图所示：

一种有效方案如下图所示，可以证明最少使用魔法修改次数为 2，使得能够到达 (3, 3) 。