普及-⏱ 1000ms💾 256MB#P3189🏷️ 搜索深度优先搜索

题目描述

配电网的检修井布在 $n \times n$ 的网格上,. 为可通行井,# 为带电危险井。 检修员要从 $A$ 井走到 $B$ 井,每步只能走上、下、左、右相邻的一格。 若 $A$ 或 $B$ 本身是危险井,则视为无法完成。

多组数据,判断能否从 $A$ 走到 $B$。坐标均从 $0$ 开始计数。

输入格式

第一行一个整数 $k$,为数据组数。 每组数据:第一行一个正整数 $n$;接下来 $n$ 行,每行 $n$ 个 . 或 #; 最后一行四个整数 $ha, la, hb, lb$,分别为 A 与 B 的行、列坐标。

输出格式

每组数据一行:能到达输出 YES,否则输出 NO。

数据范围

$$1 \le n \le 100$$
,坐标在网格内。

样例输入 #1
2
3
.##
..#
#..
0 0 2 2
5
.....
###.#
..#..
###..
...#.
0 0 4 0
样例输出 #1
YES
NO
样例输入 #2
1
1
.
0 0 0 0
样例输出 #2
YES