1825: 蓝桥杯2015年第六届真题-穿越雷区（Python3）DFS方法

解题思路:
DFS寻找最短路径。

注意事项:

1.每次递归传入上次的步数，如果到达终点，再判断此路径是否最短；

2.递归时同时传入上次坐标中的符号值，用于判断路径是否符合要求，不符合直接退出该函数；

3.每次走下一步之前需要判断下一步的索引是否合法；

4.本题可以走四个方向，可以用循环的方式代替写四次dfs()的方法。

参考代码:

def dfs(x=0, y=0, last_flag='A', step=0):
    global map_, visited, around, res
    if last_flag == 'B':
        res = min(res, step)
        return
    if visited[x][y] is False:
        visited[x][y] = True
        for coordinate in around:
            if 0 <= x + coordinate[0] < n and 0 <= y + coordinate[1] < n:  # index
                if map_[x + coordinate[0]][y + coordinate[1]] != last_flag and \
                        visited[x + coordinate[0]][y + coordinate[1]] is False:
                    dfs(x + coordinate[0], y + coordinate[1],
                        map_[x + coordinate[0]][y + coordinate[1]], step + 1)
        visited[x][y] = False


import math
n = int(input())
map_, res, temp = [list(input().split()) for _ in range(n)], math.inf, 0
visited = [[False for _ in range(n)] for _ in range(n)]
around = [[0, 1], [1, 0], [0, -1], [-1, 0]]  # R, D, L, U
dfs()
if res != math.inf:
    print(res)
else:
    print(-1)