1792迷宫基本算法之搜索

1792:迷宫

总时间限制: 3000ms 内存限制: 65536kB
描述
一天Extense在森林里探险时不小心走入了一个迷宫。这个迷宫由n x n个格子组成，每个格子有两种状态：.表示通路#表示不通路。Extense只能从相邻的上下左右四个方向移动。如果起点或终点所在格子为#则视为无法到达。
输入
第一行为测试用例的数量k。接下来是k个测试用例的数据。每个测试用例的第一行为一个整数n（1 <= n <= 100）表示迷宫规模为n x n格子。第二行给出n x n大小的字符矩阵仅包含.或#两种字符。第三行为四个整数ha la hb lb分别表示A位于第ha行, 第la列的位置B位于第hb行, 第lb列的位置（注意索引从零开始）。
输出
共k行每行为对应测试用例的结果能到达则输出"YES"否则输出"NO"

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

样例输出
YES
NO

关键点：

在迷宫设计中存在两种基本的出题策略：一种是判断目标点是否可达（例如本题的情况），另一种则是计算所有相互连通的区域数量。这些题目通常采用深度优