[蓝桥杯] 穿越雷区 (Python 实现)

x33g5p2x  于2022-02-22 转载在 Python  
字(0.8k)|赞(0)|评价(0)|浏览(438)

题目:
X 星的坦克战车很奇怪,它必须交替地穿越正能量辐射区和负能量辐射区才能保持正常运转,否则将报废。
某坦克需要从 A 区到 B 区去(A,B 区本身是安全区,没有正能量或负能量特征),怎样走才能路径最短?
已知的地图是一个方阵,上面用字母标出了 A,B 区,其它区都标了正号或负号分别表示正负能量辐射区。

例如:

坦克车只能水平或垂直方向上移动到相邻的区。

输入格式
第一行是一个整数 n,表示方阵的大小。
接下来是 n 行,每行有 n 个数据,可能是 A,B,+,- 中的某一个,中间用空格分开。A,B 都只出现一次。

输出格式

一个整数,表示坦克从 A 区到 B 区的最少移动步数。如果没有方案,则输出 −1。

数据范围

4≤n<100

输入样例:

输出样例:
10

代码:

  1. n = int(input())
  2. matrix = []
  3. for _ in range(n):
  4. temp = list(map(str, input().split(' ')))
  5. matrix.append(temp)
  6. path = [[False] * n for _ in range(n)]
  7. def search (y, x, res):
  8. save = []
  9. save.append((y, x, res))
  10. path[y][x] = True
  11. while save:
  12. front = save.pop(0)
  13. y, x, res = front
  14. if matrix[y][x] == 'B':
  15. return res
  16. for dy, dx in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
  17. ny, nx = dy+y, dx+x
  18. if -1 < ny < n and -1 < nx < n and not path[ny][nx] and matrix[y][x] != matrix[ny][nx]:
  19. path[ny][nx] = True
  20. save.append((ny, nx, res+1))
  21. return -1
  22. for y in range(n):
  23. for x in range(n):
  24. if matrix[y][x] == 'A':
  25. print(search(y, x, 0))

相关文章