广度优先搜索
描述有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++写 #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 != '2') {
q.push(s + "2");
}
}
}
}
int main() {
int n;
cin >> n;
bfs(n);
return 0;
}
页:
[1]