题目描述：
话说大诗人李白，一生好饮。幸好他从不开车。
无事街上走，提壶去打酒。 逢店加一倍，遇花喝一斗。 这一路上，他一共遇到店5次，遇到花10次，已知最后一次遇到的是花，他正好把酒喝光了。 请你计算李白遇到店和花的次序，可以把遇店记为a，遇花记为b。则：babaabbabbabbbb 就是合理的次序。像这样的答案一共有多少呢？请你计算出所有可能方案的个数（包含题目给出的）。 注意：通过浏览器提交答案。答案是个整数。不要书写任何多余的内容。
首先说一下自己其中一个错误的思路，收到前面做的象棋的影响，把整个局面想象成了一个map，2×15，其中第一列为a第二列为b，利用DFS搜索之后发现有很多重复的字符串，还得判重，非常的麻烦，最终放弃，贴上第一次DFS的错误代码。(2017/3/12)
第二次将打酒的过程想想成一棵二叉树，向左边分叉，向右边分叉，DFS遍历出所有5个a，10个b的结果，然后用solve() 处理遍历出来的字符串，不得不说，个人感觉最大的坑是处理字符串，原来以为打酒的过程喝没了即wine中途为0，这种搜索出来的结果是不正确的，接受的条件只能是最后一次打酒后wine为0。网上有大牛更简洁的代码，个人喜欢用处理字符串的方式，就用了solve() ，当然也可以不用，个人喜好。（附上本人渣代码2017/3/13）
//错误的示例，后续提醒自己不要犯错2017/3/12 #include <iostream> #include <cmath> using namespace std; char mapAlpha[15][2] = { '\0' }; char alpha[15] = { '\0' }; bool idx[15][2] = { false }; int count = 0; int solve() { int res = 0; for (int i = 0; i < 16; i++) { if (alpha[i] == 'a') { res *= 2; } else { if (res > 0) { res--; } } } if (res == 0) { cout << "ok" << endl; count++; } } void dfs(int i, int j, int k) { //出界条件 if (i < 0 || i > 14 || j < 0 || j > 1) { return; } idx[i][j] = true; //idx标记访问过的数组 alpha[k - 1] = mapAlpha[i][j]; if (k == 15) //当搜索到一个字符串时查看剩余酒量 { solve(); return; } for (int x = 0; x <= 1; x++) { for (int y = -1; y <= 1; y++) { if (x != -1 && abs(x) + abs(y) != 0 && idx[i + x][j + y] == false) { idx[i + x][j + y] = true; dfs(i + x, j + y, k + 1); idx[i + x][j + y] = false; } } } } int main() { //初始化map for (int i = 0; i < 15; i++) { for (int j = 0; j < 2; j++) { if (j == 0) { mapAlpha[i][j] = 'a'; } else { mapAlpha[i][j] = 'b'; } } } dfs(0, 0, 1); //初始遍历位置 dfs(0, 1, 1); cout<<"count: "<<count<<endl; return 0; }正确的思路
// 2017/3/13 #include <iostream> using namespace std; char chr[15]; int count = 0; //处理DFS搜索的字符串，有坑 void solve() { int res = 2; int ok = 1; for (int i = 0; i < 15; i++) { if (chr[i] == 'a') { res *= 2; if (i != 14 && res == 0) { ok = 0; } } else if (chr[i] == 'b') { res--; if (i != 14 && res == 0) { ok = 0; } } } if (res == 0 && chr[14] == 'b' && ok) { count++; cout << chr << endl; } } void dfs(int store, int flower, int k) { if (flower > 10 || store > 5) //越界的条件 { return; } if (store == 5 && flower == 10 && k == 15) //最后一次返回条件，返回一个遍历后的字符串 { solve(); return; } chr[k] = 'a'; //二叉树的左侧分叉 dfs(store + 1, flower, k + 1); chr[k] = 'b'; //二叉树的右侧分叉 dfs(store, flower + 1, k + 1); } int main() { dfs(0, 0, 0); cout << "count: " << count << endl; return 0; }