广度优先搜索

黎子卿

描述
有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

1. #include <iostream>
   
2. #include <queue>
   
3. #include <string>
   
4. using namespace std;
   
5. 
   
6. void bfs(int n) {
   
7.     queue<string> q;
   
8.     q.push("");
   
9.     while (!q.empty()) {
   
10.         string s = q.front();
    
11.         q.pop();
    
12.         if (s.length() == n) {
    
13.             cout << s << endl;
    
14.         } else {
    
15.             q.push(s + "1");
    
16.             if (s.length() == 0 || s[s.length() - 1] != '2') {
    
17.                 q.push(s + "2");
    
18.             }
    
19.         }
    
20.     }
    
21. }
    
22. 
    
23. int main() {
    
24.     int n;
    
25.     cin >> n;
    
26.     bfs(n);
    
27.     return 0;
    
28. }
    

复制代码