简单迷宫问题[3]
测试数据来自 system/2440
作业已超过截止时间,您无法递交本题目。
时间限制:1秒 内存限制:256M
【问题描述】
一天小H 在森林里探险的时候不小心走入了一个迷宫,迷宫可以看成是由 \(n × n\) 的格点组成,每个格点只有 2 种状态:. 和 '#',前者表示可以通行后者表示不能通行。同时当小H 处在某个格点时,他只能移动到东南西北(或者说上下左右)四个方向之一的相邻格点上,小H想要从点 A 走到点 B,问在不走出迷宫的情况下能不能办到。如果起点或者终点有一个不能通行(为 '#'),则看成无法办到。
【输入格式】
第 1 行是测试数据的组数k,后面跟着 \(k\) 组输入。
每组测试数据的第 1 行是一个正整数 \(n\) ,表示迷宫的规模是 \(n × n\) 的。
接下来是一个 \(n × n\) 的矩阵,矩阵中的元素为'.' 或 '#'。再接下来一行是 4 个整数 \(x_a, y_a, x_b, y_b\),描述 A 处在第 \(x_a\) 行, 第 \(y_a\) 列,B 处在第 \(x_b\) 行, 第 \(y_b\) 列。注意到 \(x_a, y_a, x_b, y_b\) 全部是从 0 开始计数的。
【输出格式】
\(k\) 行:每行输出对应一个输入。能办到则输出“YES”,否则输出“NO”。
【输入输出样例】
Input
2
3
.##
..#
#..
0 0 2 2
5
.....
###.#
..#..
###..
...#.
0 0 4 0
Output
YES
NO
【数据说明】
对于所有数据保证 \(1 ≤ n ≤ 100\)。
【来源】
Mr.he