广度优先搜索

黎子卿

描述
有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
提示
可以用广度优先搜索

isdkz

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)

tommyyu

#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[i]-'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[0]), 2); ++j) {
                        string temp = now_path[0] + 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[i] << endl;
        }
        return 0;
}