#P18214. Judgement

Judgement

Judgement

青山和她的朋友丹尼尔创造了一款名为“大将军”的单人游戏,玩家可以在网格上绘制图案。

游戏在一个 n×mn\times m 的网格上进行。每个格子的颜色为红色、蓝色或白色。初始时,格子 (a,b)(a,b) 为红色,格子 (c,d)(c,d) 为蓝色,其余格子均为白色,且这两个格子不同。我们把这两个格子称为特殊格子,其他格子称为非特殊格子。

一次操作如下:

  1. 选择一个非特殊格子 (x,y)(x,y)。
  2. 选择一个与它有公共边的格子 (x′,y′)(x',y'),要求该格子当前不是白色。
  3. 把 (x,y)(x,y) 涂成 (x′,y′)(x',y') 当前的颜色。

非特殊格子可以被反复涂色,新颜色覆盖旧颜色;两个特殊格子的颜色始终不能改变。玩家可以执行任意次数的操作,也可以不执行操作,然后停止游戏。

现在给出停止时的网格状态。请判断它能否通过上述合法操作得到。

输入格式

第一行包含一个整数 TT,表示测试用例数。

每个测试用例的格式如下:

  • 第一行包含两个整数 n,mn,m;
  • 第二行包含四个整数 a,b,c,da,b,c,d,依次给出红色和蓝色特殊格子的位置;
  • 接下来 nn 行,每行包含 mm 个字符,描述目标网格。R 表示红色,B 表示蓝色,. 表示白色。

保证 (a,b)≠(c,d)(a,b)\ne(c,d),且目标网格中 (a,b)(a,b) 为 R、(c,d)(c,d) 为 B。

输出格式

对每个测试用例输出一行:如果目标状态可以合法得到,输出 YES;否则输出 NO。输出字母可以使用任意大小写形式。

数据范围

  • 1≤T≤1041\le T\le10^4;
  • 1≤n,m≤5001\le n,m\le500,且 n⋅m≥2n\cdot m\ge2;
  • 1≤a,c≤n1\le a,c\le n,1≤b,d≤m1\le b,d\le m;
  • 所有测试用例的 n⋅mn\cdot m 之和不超过 250000250000。

样例

4
3 3
1 1 1 2
RBB
RRR
BBR
6 6
1 1 6 6
RRRRRR
BBBBBR
BRRRBR
BRBBBR
BRRRRR
BBBBBB
5 5
3 3 4 4
BBR.B
BBR.B
RRR.B
...BB
BBBB.
1 5
1 1 1 3
RBBBR
YES
YES
NO
NO

样例说明

下图给出了第一个测试用例的一种合法构造过程。皇冠标记两个特殊格子。

原题中的合法构造过程