蓝桥杯2015年第六届真题-穿越雷区

解题思路:

先找到坦克的起始点，用变量记录下来。用广搜 -dfs的方式解决。

题的目标：最少移动步数数 有则输出无则输出-1

dfs的技巧：

先开栈避免因数据规模太大递归次数太多而出现爆栈的情况，分不清是记忆化搜索还是不是记忆化搜索那就直接写上lru_cache(maxsize=None）

分析：

坦克只能是所在位置与下一个位置不同时才能行走所以要判断Map[xx][yy]是否与Map[x][y]相等，相等要跳过，不相等给走过的位置打商标机然后dfs(xx,yy,depth+1) 最后再清除标记。

坦克可以上下左右移动所以要设置一个移动数组dirt = [[0, 1], [0, -1], [1, 0], [-1, 0]]遍历数组代表了向四周移动，注意要判断边界

注意事项:

标记数组一定要用列表推导式写，不然会出错，具体原因我也不知道
参考代码:

from functools import lru_cache
import sys
#明天来了给走过的路径打标记，回去睡觉
sys.setrecursionlimit(1000000)


@lru_cache(maxsize=None)
def dfs(x, y, depth):
   global ans
   if depth > ans:
       return

   if x == x2 and y == y2:
       ans = min(ans, depth)
       return
   for i in range(4):
       xx = x + dirt[i][0]
       yy = y + dirt[i][1]
       if 0 <= xx < n and 0 <= yy < n:
           if vis[xx][yy]==True:
               continue
           if Map[xx][yy] != Map[x][y]:
               vis[xx][yy]=True
               dfs(xx, yy, depth + 1)
               vis[xx][yy]=False


n = int(input())
Map = []
for i in range(n):
   Map.append(list(input().split()))
x1, y1, x2, y2 = 0, 0, 0, 0
for i in range(n):
   for j in range(n):
       if Map[i][j] == "A":
           x1 = i
           y1 = j
       if Map[i][j] == 'B':
           x2 = i
           y2 = j
dirt = [[0, 1], [0, -1], [1, 0], [-1, 0]]
vis=[[False]*n for _ in range(n)]
#bi标记数组一定要用推导式写，不然会出现错误
#vis=[[False]*n]*n
ans = 10000000000
dfs(x1,y2,0)
if ans==10000000000:
   ans=-1
else:
   ans
print(ans)