python/TangDou/AcWing/DieDaiJiaShen/170_bfs.cpp

#include <bits/stdc++.h>

using namespace std;
typedef short int int16; //使用短整型，以防止MLE
const int N = 110;       //数组上限
const int M = 100;       //极限值n的上限

int n;     //输出以数字n结尾的加法链
int cnt;   //已经完成预处理的数字个数，当n=M时，表示所有范围内的数字均已成功生成加法链

queue<vector<int16>> q; //以动态数组记录状态
vector<int16> ans[N];   //二维数组，第一维记录是哪个数，第二维是一个动态数组，描述第一维的数是怎么构建的加法链路径

int main() {
    // 一、预处理出M以内的所有 加成序列
    // bfs
    q.push({1}); //从{1} 出发宽搜
    while (q.size()) {
        auto a = q.front();
        q.pop();

        int16 v = a[a.size() - 1]; //最后一位的填充值

        // 如果没有计算过，那么现在是第一次到达，最短路径，记录已计算过
        // 并且,记录 ans[v]的最短路径就是a这个动态数组
        if (!ans[v].size()) ans[v] = a, cnt++; // cnt++　：v这个数计算完成，数量++

        //从数组状态a开始扩展，下面的办法就统一扩展了一位，然后后面的循环中，都使用这一位
        vector<int16> x = a;
        x.emplace_back(0); // emplace_back()是c++11的新特性,可以理解为push_back的加强版本

        for (int i = a.size() - 1; i >= 0; i--) {
            int16 s = v + a[i];     // a[n]肯定由a[n-1]+?得到
            if (s > M) continue;    // 冒了肯定没用
            x[a.size()] = s;        // 构建新状态
            q.push(x);              // 入队列等待扩展
        }
        //已经计算完M个，可以结束了
        if (cnt == M) break;
    }
    // 二、输入n 后查表
    while (scanf("%d", &n) && n) {
        for (int i : ans[n]) printf("%d ", i);
        puts("");
    }
    return 0;
}