No submission language available for this problem.

题目描述

假设你是一名建筑师，你的客户想要在一个大型的工业园区中建造一座新的工厂。在这个工业园区中，有很多道路和建筑物，你需要找到一条从工厂出发，到达原材料仓库的最短路径。但是在这个园区中有很多区域是无法通行的，因此你需要设计一个算法来判断是否有一条可行的路径从工厂到仓库。

这个地图可看成 $n\times n$ 的格点，这些格点只有 2 种状态：

• . 表示可通行
• # 表示不可通行

从任意一个格点出发，只能往该格点的上下左右四个相邻格点上

问，若想在不走出地图的情况下，从工厂 走到仓库能不能办到。如果起点或者终点有一个不能通行 (为 # )，则看成无法办到。

输入

第 $1$ 行是测试数据的组数 $K$，后面是 $K$ 组输入。

每组测试数据的第 $1$ 行是一个正整数 $n$ $(1 ≤ n ≤ 100)$，表示地图的规模是 $n\times n$ 的。接下来是一个 $n\times n$ 的矩阵，矩阵中的元素为 . 或者 # 。再接下来一行是 4 个整数 $x_1, y_1$, $x_2, y_2$，描述工厂处在第 $x_1$ 行, 第 $y_1$列，仓库在第 $x_2$ 行, 第 $y_2$ 列。注意到 $x_1, y_1$, $x_2, y_2$ 全部是从 $0$ 开始计数的。

输出

$k$ 行，每行输出对应一个输入。能办到则输出 "YES"，否则输出 "NO"。

样例

2
3
.##
..#
#..
0 0 2 2
5
.....
###.#
..#..
###..
...#.
0 0 4 0

YES
NO