求助：JavaScript实现二维数组交替A/B最短路径的图结构方案

绝对有！这个问题用**广度优先搜索（BFS）**来解决简直完美——这是找无权图最短路径的标准方案，刚好契合你要求的A/B交替行走规则。咱们可以把二维数组里的每个格子直接当成图的节点，相邻（上下左右）且符合交替要求的格子之间视为有一条边，然后用BFS从左上角起点遍历到右下角终点，第一次到达终点时的步数就是最小步数。

1. 图的建模方式 #

• 数组中的每个格子 (i,j) 就是图的一个节点
• 节点之间的边规则：如果当前格子是A，它只能和上下左右相邻的B格子相连；如果当前是B，则只能和相邻的A格子相连
• 每走一步对应从一个节点移动到相邻的符合规则的节点，步数+1

2. BFS的核心逻辑 #

BFS天生适合最短路径问题，因为它是按层遍历的，第一次抵达终点时的步数必然是最小的。具体步骤如下：

• 初始化一个队列，把起点(0,0)和初始步数0放入队列
• 准备一个访问矩阵，标记已经走过的格子，避免重复访问（防止陷入循环）
• 每次从队列头部取出一个节点，先检查是不是终点(4,4)（你的数组是5x5），如果是直接返回当前步数
• 遍历当前节点的四个相邻方向，对每个相邻格子做三个检查：
  • 是否在数组范围内（不越界）
  • 是否未被访问过
  • 是否和当前格子的值交替（比如当前是A，相邻必须是B）
• 符合所有条件的格子标记为已访问，步数+1后加入队列

3. 可运行的代码示例 #

def find_shortest_path(grid):
    rows = len(grid)
    cols = len(grid[0])
    # 定义四个移动方向：上、下、左、右
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    from collections import deque
    # 队列元素：(行索引, 列索引, 当前步数)
    queue = deque()
    queue.append((0, 0, 0))
    # 访问矩阵，记录已走过的格子
    visited = [[False for _ in range(cols)] for _ in range(rows)]
    visited[0][0] = True
    
    while queue:
        i, j, current_steps = queue.popleft()
        
        # 到达右下角终点，返回当前步数
        if i == rows - 1 and j == cols - 1:
            return current_steps
        
        # 遍历四个方向
        for di, dj in directions:
            new_i = i + di
            new_j = j + dj
            
            # 检查边界、未访问、值交替三个条件
            if 0 <= new_i < rows and 0 <= new_j < cols:
                if not visited[new_i][new_j] and grid[new_i][new_j] != grid[i][j]:
                    visited[new_i][new_j] = True
                    queue.append((new_i, new_j, current_steps + 1))
    
    # 如果不存在路径（你的示例中不会触发）
    return -1

# 测试你的二维数组
test_grid = [
    ['A', 'A', 'A', 'B', 'A'],
    ['B', 'B', 'B', 'B', 'B'],
    ['A', 'B', 'A', 'A', 'A'],
    ['A', 'B', 'B', 'B', 'B'],
    ['A', 'A', 'A', 'A', 'A']
]
print(find_shortest_path(test_grid))  # 输出：13

为什么这个方案简单高效？ #

• 不需要额外构建复杂的图结构，直接用原数组和访问矩阵就能代表图的节点与连接关系
• BFS逻辑直观易懂，没有递归或复杂的状态计算，新手也能快速理解
• 时间复杂度为O(rows*cols)，对于你的5x5数组来说完全无压力，就算是更大规模的数组也能高效运行

内容的提问来源于stack exchange，提问作者Boris Grunwald