问题分析

这个问题的核心是找到 唐僧 从一个起点（源节点）到终点（目标节点）在一个图中的最短路径，并且还要求每次遇到的敌人都要“消除”掉。

我们可以把这个问题建模成一个 图，其中每个节点代表一个位置，边代表相邻的两个位置之间可以行走的路径。

思路

  • 图的表示：给定的是一个二维平面，唐僧需要在这个平面中行走，平面上的每个点都有敌人。我们需要求解唐僧从起点到终点的最短路径，其中每次遇到敌人时需要消除他们。消除敌人可以通过 BFS（广度优先搜索）来实现。
  • BFS：我们可以利用广度优先搜索（BFS）来找到最短路径。在 BFS 中，节点的扩展是层次性的，保证了我们每次扩展时都是找到了当前的最短路径。

BFS 方法介绍

  • 队列：BFS 使用队列来存储要扩展的节点。每次从队列中取出一个节点，检查它的四个方向（上、下、左、右）是否可以访问。
  • 图的状态：我们会维护一个 二维数组 visited 来记录每个位置是否已经访问过。

具体步骤

  1. 初始化起点，并将其加入队列。
  2. 每次从队列中取出一个位置，检查其四个相邻位置是否有效并且未访问过。
  3. 如果一个相邻位置是敌人，并且能消除敌人，则将其标记为访问过。
  4. 遇到终点时，返回路径长度。

代码实现

from collections import deque

# 定义四个方向：上、下、左、右
DIRECTIONS = [(-1, 0), (1, 0), (0, -1), (0, 1)]

def bfs(grid, start, end):
    n, m = len(grid), len(grid[0])
    # 初始化访问状态数组
    visited = [[False for _ in range(m)] for _ in range(n)]
    
    # 队列中存储的是(当前行，当前列，步数)
    queue = deque([(start[0], start[1], 0)])
    visited[start[0]][start[1]] = True
    
    while queue:
        x, y, steps = queue.popleft()
        
        # 如果到了终点
        if (x, y) == end:
            return steps
        
        # 尝试四个方向
        for dx, dy in DIRECTIONS:
            nx, ny = x + dx, y + dy
            
            # 检查是否在地图内并且没有访问过
            if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny]:
                # 如果是敌人，则消除敌人
                if grid[nx][ny] == 1:  # 假设敌人标记为1
                    visited[nx][ny] = True
                    queue.append((nx, ny, steps + 1))
                elif grid[nx][ny] == 0:  # 如果是空白，直接进入
                    visited[nx][ny] = True
                    queue.append((nx, ny, steps + 1))
    
    # 如果没有找到路径
    return -1

# 主函数
def main():
    # 例如：一个5x5的地图
    grid = [
        [0, 1, 0, 0, 0],  # 0: 空白，1: 敌人
        [0, 1, 0, 1, 0],
        [0, 0, 0, 1, 0],
        [1, 1, 0, 0, 0],
        [0, 0, 0, 1, 0]
    ]
    
    start = (0, 0)  # 起点
    end = (4, 4)  # 终点
    
    # 计算最短路径
    result = bfs(grid, start, end)
    
    if result == -1:
        print("No path found.")
    else:
        print(f"The shortest path length is: {result}")

if __name__ == "__main__":
    main()

代码解释

  1. 输入数据：这里我们假设地图是一个二维矩阵，0 表示空地，1 表示敌人。
  2. BFS 函数：bfs 函数实现了广度优先搜索。它接收一个 grid（地图），start（起点），end（终点）作为输入，返回从起点到终点的最短路径长度。
  3. 队列：queue 中存储的是当前节点的坐标和步数。每次从队列中取出一个节点，检查其四个方向的邻居节点。
  4. 访问状态：visited 数组用于标记每个位置是否已经访问过。
  5. 返回结果：如果找到了终点，返回步数；如果遍历完所有节点都没有找到终点，返回 -1。

总结

  • BFS 适合用来处理图中的最短路径问题。
  • 每次扩展节点时，BFS 都是层次性的，这意味着每次扩展时一定是最短路径。
  • 本问题的关键是理解如何在 BFS 中处理 敌人消除，并且如何使用 BFS 遍历所有可能的路径。