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

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

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

例如:

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

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

输出格式

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

数据范围

4≤n<100

输入样例:

输出样例:
10

代码:

n = int(input())
matrix = []
for _ in range(n):
    temp = list(map(str, input().split(' ')))
    matrix.append(temp)
path = [[False] * n for _ in range(n)]   
    
def search (y, x, res):
    save = []
    save.append((y, x, res))
    path[y][x] = True
    
    while save:
        front = save.pop(0)
        y, x, res = front
        if matrix[y][x] == 'B':
            return res
        for dy, dx in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
            ny, nx = dy+y, dx+x
            if -1 < ny < n and -1 < nx < n and not path[ny][nx] and matrix[y][x] != matrix[ny][nx]:
                path[ny][nx] = True
                save.append((ny, nx, res+1))
    return -1
for y in range(n):
    for x in range(n):
        if matrix[y][x] == 'A':
            print(search(y, x, 0))

相关文章