4204: §2 5 迷宫
[Creator : ]
Description
一天 Extense 在森林里探险的时候不小心走入了一个迷宫,迷宫可以看成是由 $n \times n$ 的格点组成,每个格点只有 $2$ 种状态,. 和 #,前者表示可以通行后者表示不能通行。
同时当 Extense 处在某个格点时,他只能移动到东南西北(或者说上下左右)四个方向之一的相邻格点上。
Extense 想要从点 $A$ 走到点 $B$,问在不走出迷宫的情况下能不能办到。如果起点或者终点有一个不能通行(为 #),则看成无法办到。
同时当 Extense 处在某个格点时,他只能移动到东南西北(或者说上下左右)四个方向之一的相邻格点上。
Extense 想要从点 $A$ 走到点 $B$,问在不走出迷宫的情况下能不能办到。如果起点或者终点有一个不能通行(为 #),则看成无法办到。
Input
第 $1$ 行是测试数据的组数 $k$,后面跟着 $k$ 组输入。
每组测试数据的第 $1$ 行是一个正整数 $n\ (1 ≤ n ≤ 100)$,表示迷宫的规模是 $n \times n$ 的。
接下来是一个 $n \times n$ 的矩阵,矩阵中的元素为 . 或者 # 。
再接下来一行是 $4$ 个整数 $h_a,\ l_a,\ h_b,\ l_b$,描述 $A$ 处在第 $h_a$ 行,第 $l_a$ 列,$B$ 处在第 $h_b$ 行,第 $l_b$ 列。注意到 $h_a,\ l_a,\ h_b,\ l_b$ 全部是从 $0$ 开始计数的。
每组测试数据的第 $1$ 行是一个正整数 $n\ (1 ≤ n ≤ 100)$,表示迷宫的规模是 $n \times n$ 的。
接下来是一个 $n \times n$ 的矩阵,矩阵中的元素为 . 或者 # 。
再接下来一行是 $4$ 个整数 $h_a,\ l_a,\ h_b,\ l_b$,描述 $A$ 处在第 $h_a$ 行,第 $l_a$ 列,$B$ 处在第 $h_b$ 行,第 $l_b$ 列。注意到 $h_a,\ l_a,\ h_b,\ l_b$ 全部是从 $0$ 开始计数的。
Output
$k$ 行,每行输出对应一个输入。
能办到则输出 $\text{YES}$,否则输出 $\text{NO}$。
能办到则输出 $\text{YES}$,否则输出 $\text{NO}$。
Sample 1 Input
2
3
.##
..#
#..
0 0 2 2
5
.....
###.#
..#..
###..
...#.
0 0 4 0
Sample 1 Output
YES
NO