广度优先搜索

黎子卿

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

1. from collections import deque
   
2. 
   
3. def bfs(n):
   
4.     result = []
   
5.     queue = deque([(('', 0))])  # (当前走法, 当前位置)
   
6.     while queue:
   
7.         path, pos = queue.popleft()
   
8.         if pos == n:
   
9.             result.append(path)
   
10.         if pos + 1 <= n:
    
11.             queue.append((path + '1', pos + 1))
    
12.         if pos + 2 <= n:
    
13.             queue.append((path + '2', pos + 2))
    
14.     result.sort(key=lambda x: (len(x), x))
    
15.     return result
    
16. 
    
17. n = 4
    
18. result = bfs(n)
    
19. for r in result:
    
20.     print(r)
    

复制代码

tommyyu

1. #include <iostream>
   
2. #include <vector>
   
3. #include <string>
   
4. #include <algorithm>
   
5. using namespace std;
   
6. vector<string> paths;
   
7. int n;
   
8. bool cmp(string a, string b) {
   
9.         if(a.length() != b.length()) return a.length() < b.length();
   
10.         return a < b;
    
11. }
    
12. int sum_(string a) {
    
13.         int ans = 0;
    
14.         for(int i=0; i<a.size(); ++i) ans += (a[i]-'0');
    
15.         return ans;
    
16. }
    
17. void bfs(vector<string>& now_path) {
    
18.         if(now_path.size() == 0) {
    
19.                 return;
    
20.         }
    
21.         int x = now_path.size();
    
22.         for(int i=0; i<x; ++i) {
    
23.                 for(int j=1; j<=min(n-sum_(now_path[0]), 2); ++j) {
    
24.                         string temp = now_path[0] + char(j+'0');
    
25.                         if(sum_(temp) == n)
    
26.                                 paths.push_back(temp);
    
27.                         else
    
28.                                 now_path.push_back(temp);
    
29.                 }
    
30.                 now_path.erase(now_path.begin());
    
31.         }
    
32.         bfs(now_path);
    
33. }
    
34. int main()
    
35. {
    
36.         vector<string> now_path;
    
37.        
    
38.         cin >> n;       
    
39.        
    
40.         if(n>0) now_path.push_back("1");
    
41.         if(n>1) now_path.push_back("2");
    
42.         bfs(now_path);
    
43.         sort(paths.begin(), paths.end(), cmp);
    
44.        
    
45.         for(int i=0; i<paths.size(); ++i) {
    
46.                 cout << paths[i] << endl;
    
47.         }
    
48.         return 0;
    
49. }

复制代码