蓝桥杯训练15——穿越雷区

Source

from collections import deque

def bfs(leiqu):
    n = len(leiqu)
    
    # 定义四个方向:右、下、左、上
    directions=[(0,1),(0,-1),(1,0),(-1,0)]
    
    # 初始化访问标记矩阵
    visited = [[False] * n for _ in range(n)]
    queue = deque()
    # 找到起点 A 和终点 B 的位置
    for i in range(n):
        for j in range(n):
            if leiqu[i][j] == 'A':
                start = (i, j)
            elif leiqu[i][j] == 'B':
                end = (i, j)
    

    # 初始化队列,将起点加入队列
    
    queue.append((start, 0, leiqu[start[0]][start[1]]))
    
    # 开始 BFS
    while queue:
        (x, y), step, current_energy = queue.popleft()
        
        # 标记当前节点为已访问
        visited[x][y] = True
        
        # 遍历四个方向
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            
            # 检查新节点是否在矩阵范围内且未被访问过
            if 0 <= nx < n and 0 <= ny < n and not visited[nx][ny]:
                next_energy = leiqu[nx][ny]
                
                # 检查能量区是否与当前节点的能量区不同
                if next_energy != current_energy:
                    # 如果找到了终点 B,返回步数
                    if (nx, ny) == end:
                        return step + 1
                    
                    # 将新节点加入队列
                    visited[nx][ny] = True
                    queue.append(((nx, ny), step + 1, next_energy))
    
    # 如果遍历完所有可能的路径都没有找到 B,返回 -1
    return -1

# 读取输入
n = int(input())
leiqu = [input().split() for _ in range(n)]

# 调用 BFS 函数并输出结果
result = bfs(leiqu)
print(result)