NOI 2.5.1792迷宫题解

题目

1792:迷宫
总Time Limit: 3000ms Memory Limit: 65536kB
Description
某日，Extense在森林中探险时意外进入了一个迷宫。该迷宫可视为由n乘n的格点构成，每个格点存在两种状态，分别为.与#，其中.代表可通过区域，#则表示不可通行区域。当Extense处于某一格点时，他仅能向东南西北四个方向（即上下左右）移动至相邻的格点。Extense的目标是从起点A出发抵达终点B，要求在不超出迷宫范围的前提下判断是否能够实现。若起点或终点中任意一个为不可通行状态（即标记为#），则视为无法完成目标。

Input
第一行给出测试数据的组数k，随后依次输入k组数据。每组数据的第一行包含一个正整数n（1 <= n <= 100），用于描述迷宫的规模为n乘n。接下来是一个由n乘n元素组成的矩阵，矩阵中的每个元素为.或#。随后一行给出四个整数ha, la, hb, lb，分别表示起点A位于第ha行、第la列，终点B位于第hb行、第lb列。需注意的是ha、la、hb和lb均以0作为起始编号。

Output
输出k行内容，每行对应一组输入结果。若可行则输出“YES”，否则输出“NO”。

思路

初看此问题，似乎可以借鉴流感传播的处理方式。具体而言，在输入数据后，首先将起始位置标记为0，随后如同病毒传播一般