BFS Shortest Path

原始题目：LeetGPU - BFS Shortest Path

题目描述

使用广度优先搜索（BFS）在无权重二维网格中寻找最短路径。给定带有障碍物的网格和起点/终点位置，返回到达目的地所需的最少步数。网格中 0 表示可通过，1 表示障碍物。允许向四个方向移动（上、下、左、右）。若无路径存在，返回 -1。

实现要求

• 不允许使用外部库。
• solve 函数签名必须保持不变。
• 若起点和终点相同，返回 0。

示例

示例 1

grid (4×4): [[0,0,0,0],[1,1,0,1],[0,0,0,0],[0,1,1,0]]
start (0,0), end (3,3)
Output: 6 (路径: (0,0)→(0,1)→(0,2)→(1,2)→(2,2)→(2,3)→(3,3))

示例 2

grid (3×3): [[0,1,0],[1,1,1],[0,0,0]]
start (0,0), end (0,2)
Output: -1 (障碍物完全阻挡)

约束条件

• $1 \le rows, cols \le 1{,}000$。
• 起点和终点保证在界内且为可通过单元。
• 性能测试在 $cols = rows = 500$ 下进行。

解题思路

BFS 在 GPU 上的经典实现是层级同步（Level-Synchronous BFS）：每轮处理当前前沿的所有节点，生成下一层前沿。每个节点由一个线程处理，探索其四个邻居。使用原子操作或双缓冲标记已访问节点以避免重复探索。核心挑战在于不规则的内存访问和负载不均衡——前沿大小在不同层级间可能剧烈变化。欢迎在 GitHub Discussions 分享你的解法。