双向 BFS

模板（JavaScript）

let queue = [begin];
let map = new Map([end]);
let states = [state1, state2]; 
let step = 0;
while (queue.length && map.size) {
    // 选择元素个数少的，进行扩充
    if (queue.length > map.size) {
        [queue, map] = [Array.from(map), new Map(queue)];
    }

    // 路径长度增加
    step++;
    // queue 中的所有元素都处理一遍，生成新的 queue。
    let len = queue.length;
    while (len--) {
        const data = queue.shift();

        // 遍历所有生成的新值
        for (let val of process(states, data)) {
            // 有交集，返回距离
            if (map.has(val)) {
                return step;
            }
            // 值合法，加入队列
            if (isValid(val)) {
                queue.push(val);
            }
        }
    }
    
}

function* process(states, data) {
    for (let state of states) {
        yield _process(state, data);
    }
}