广度优先搜索
描述有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
提示
可以用广度优先搜索 from collections import deque
def bfs(n):
result = []
queue = deque([(('', 0))])# (当前走法, 当前位置)
while queue:
path, pos = queue.popleft()
if pos == n:
result.append(path)
if pos + 1 <= n:
queue.append((path + '1', pos + 1))
if pos + 2 <= n:
queue.append((path + '2', pos + 2))
result.sort(key=lambda x: (len(x), x))
return result
n = 4
result = bfs(n)
for r in result:
print(r)
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
vector<string> paths;
int n;
bool cmp(string a, string b) {
if(a.length() != b.length()) return a.length() < b.length();
return a < b;
}
int sum_(string a) {
int ans = 0;
for(int i=0; i<a.size(); ++i) ans += (a-'0');
return ans;
}
void bfs(vector<string>& now_path) {
if(now_path.size() == 0) {
return;
}
int x = now_path.size();
for(int i=0; i<x; ++i) {
for(int j=1; j<=min(n-sum_(now_path), 2); ++j) {
string temp = now_path + char(j+'0');
if(sum_(temp) == n)
paths.push_back(temp);
else
now_path.push_back(temp);
}
now_path.erase(now_path.begin());
}
bfs(now_path);
}
int main()
{
vector<string> now_path;
cin >> n;
if(n>0) now_path.push_back("1");
if(n>1) now_path.push_back("2");
bfs(now_path);
sort(paths.begin(), paths.end(), cmp);
for(int i=0; i<paths.size(); ++i) {
cout << paths << endl;
}
return 0;
}
页:
[1]