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）：每轮处理当前前沿的所有节点，生成下一层前沿。每个节点由一个线程处理，探索其四个邻居。使用原子操作或双缓冲标记已访问节点以避免重复探索。核心挑战在于不规则的内存访问和负载不均衡——前沿大小在不同层级间可能剧烈变化。

代码实现

CUDA

#include <cuda_runtime.h>
__global__ void bfs_step(const int* grid, int* dist, int* frontier, int* fsize, int H, int W, int cur_d) {
    int idx=blockIdx.x*blockDim.x+threadIdx.x;
    if(idx >= *fsize) return;
    int pos = frontier[idx], r = pos / W, c = pos % W;
    int dr[]={-1,1,0,0}, dc[]={0,0,-1,1};
    for(int d=0; d<4; d++) {
        int nr=r+dr[d], nc=c+dc[d];
        if(nr>=0&&nr<H&&nc>=0&&nc<W&&grid[nr*W+nc]==0&&dist[nr*W+nc]==-1) {
            dist[nr*W+nc]=cur_d;
            int new_pos = atomicAdd(fsize, 1);
            if(new_pos < H*W) frontier[new_pos] = nr*W+nc;
        }
    }
}
extern "C" void solve(const int* grid, int* dist, int H, int W, int sr, int sc, int er, int ec) {
    int *frontier,*fsize; cudaMalloc(&frontier,H*W*sizeof(int));cudaMalloc(&fsize,sizeof(int));
    cudaMemset(dist,-1,H*W*sizeof(int));
    cudaMemset(fsize,0,sizeof(int));
    dist[sr*W+sc]=0; frontier[0]=sr*W+sc;
    cudaMemcpy(fsize,&(int){1},sizeof(int),cudaMemcpyHostToDevice);
    for(int d=1; d<=H*W; d++) {
        int cur_fsize; cudaMemcpy(&cur_fsize,fsize,sizeof(int),cudaMemcpyDeviceToHost);
        if(cur_fsize==0) break;
        bfs_step<<<(cur_fsize+255)/256,256>>>(grid,dist,frontier,fsize,H,W,d);
        cudaDeviceSynchronize();
    }
    cudaFree(frontier);cudaFree(fsize);
}

Triton

import torch
from collections import deque
def solve(grid, start, end):
    H,W=grid.shape; dist=torch.full((H,W),-1,dtype=torch.int32,device=grid.device)
    q=deque([start]); dist[start]=0
    while q:
        r,c=q.popleft()
        for nr,nc in[(r-1,c),(r+1,c),(r,c-1),(r,c+1)]:
            if 0<=nr<H and 0<=nc<W and grid[nr,nc]==0 and dist[nr,nc]==-1:
                dist[nr,nc]=dist[r,c]+1; q.append((nr,nc))
    return dist[end]