广度优先搜索

黎子卿

描述
有n（n<=10）级楼梯，每次只允许跨1步、2步，走完这n级楼梯，有多少种走法？输出所有的走法。

例如n=4时，有5种走法：22、111、121、211、1111

输出的顺序要求，先输出跨步数少的走法，再输出跨步多的走法，当跨部数相同时，按字典序从小到大输出。

输入
一个正整数n（n<=10）
输出
多行，每行是由1、2构成的数字序列，表示一种走法。先输出跨步数少的走法，再输出跨步多的走法，当跨部数相同时，按字典序从小到大输出
样例输入
4
样例输出
22
112
121
211
1111
提示
可以用广度优先搜索
C++写

isdkz

#include <iostream>
#include <queue>
#include <string>
using namespace std;

void bfs(int n) {
    queue<string> q;
    q.push("");
    while (!q.empty()) {
        string s = q.front();
        q.pop();
        if (s.length() == n) {
            cout << s << endl;
        } else {
            q.push(s + "1");
            if (s.length() == 0 || s[s.length() - 1] != '2') {
                q.push(s + "2");
            }
        }
    }
}

int main() {
    int n;
    cin >> n;
    bfs(n);
    return 0;
}