题目描述

一天Extense在森林里探险的时候不小心走入了一个迷宫，迷宫可以看成是由 n∗n 的格点组成，每个格点只有2种状态”.”和”#”，前者表示可以通行后者表示不能通行。

同时当Extense处在某个格点时，他只能移动到东南西北(或者说上下左右)四个方向之一的相邻格点上，Extense想要从点A走到点B，问在不走出迷宫的情况下能不能办到。

如果起点或者终点有一个不能通行(为#)，则看成无法办到。

注意：A、B不一定是两个不同的点。

样例

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

输出

YES
NO

python的递归深度

• C++的最大递归深度没有限制，但是每次递归时，都会消耗额外的堆栈空间，如果栈溢出了，那么程序会被终止。
• Python3.7的最大递归深度为3000（MacOS 10.15上测试）,如果超过默认最大递归深度，则程序会报maximum recursion depth exceeded in comparison,但是该递归深度可以通过sys.getrecursionlimit(N)，将最大递归深度设置为N，但是如果在深度达到N前，堆栈溢出，会报内存错误，程序也会被终止

本题的n=100的案例，采用DFS递归深度超过3000（可以换BFS解决），设置最大递归深度后通过。

算法：DFS

k = int(input().strip())
# 设置最大递归深度为10000，如果不设置，默认递归深度为3000,本题不够用
import sys
sys.setrecursionlimit(10000)
# 四个方向
rows = [-1,0,1,0]
cols = [0,-1,0,1]
# DFS搜索
def dfs(matrix,i,j,n,ex,ey,seen):
    for t in range(4):
        if not(0<=i+rows[t]<n and 0<=j+cols[t]<n):
            continue
        # 是否可以通过
        if matrix[i+rows[t]][j+cols[t]] == '#':
            continue
        # 是否到达终点
        if i+rows[t] == ex and j+cols[t] == ey:
            return True
        # 是否已经走过
        if seen[i+rows[t]][j+cols[t]] == 1:
            continue
        # 走过标记
        seen[i+rows[t]][j+cols[t]] = 1
        # 对下一个可走的位置DFS
        if dfs(matrix,i+rows[t],j+cols[t],n,ex,ey,seen):
            return True
    return False

for _ in range(k):
    n = int(input().strip())
    matrix = []
    for _ in range(n):
        temp = input().strip()
        matrix.append([temp[i] for i in range(n)])
    # 获取起点终点坐标
    sx,sy,ex,ey = list(map(int,input().strip().split()))
    # 路径记录矩阵
    seen = [[0]*n for _ in range(n)]
    # 起点一定经过了
    seen[sx][sy] = 1
    # 起点终点特例特判
    if matrix[sx][sy] == '#' or matrix[ex][ey] == '#':
        print('NO')
        continue
    if dfs(matrix,sx,sy,n,ex,ey,seen):
        print('YES')
    else:
        print('NO')