【拼多多-寻梦】扑克牌游戏

1、题目描述

小美和小白玩扑克牌游戏，每局小美N张牌，小白M张牌，自左向右排列，(1 <= M <= N <= 8)，小美需要N个回合，使用手中的牌组合成一个新的牌的序列，每个回合小美有d，l，r，三种策略。

• 选择d，小美将最左边的牌丢弃。
• 选择l，最左边的牌放在新的序列的最左边。
• 选择r，最左边的牌放在新的序列的最右边。

N个回合后，新的序列和小白的一样则胜出，假设扑克只包含1-9.

输入描述

先输入s，作为局数，（1 <= s <= 10）。
每一局，分别输入两个字符串，分别代表小美和小白的牌。

输出描述

对于每一局开始和结束，分别输出{ 和 }。
输出获胜的方案，回合策略结束输出一个空格。若多个方案获胜，请按字典序输出。

示例
输入

3
123
3
123
321
45
67

输出

{
d d l
d d r
}
{
l l l
r l l
}
{
}

2、问题描述：

3、问题关键：

1.主要是理解题意， 将手里的牌一张一张的拿出来，组成新的序列。
2.可以dfs，排列组合，将所有方案穷举出来，比较输出即可。

4、C++代码：

#include <bits/stdc++.h>

using namespace std;

int n;
string s1, s2;
vector<string> res;

void dfs(string s, string str, int u) { //s是当前新的序列，str记录方案，u代表的是第几回合。
    if (u == n)  {
        if(s == s2) 
        res.push_back(str);
        return ;
    }

    dfs(s, str + "d ", u + 1); //删除。
    dfs(s1[u] + s, str + "l ", u + 1);//放在左边。
    dfs(s + s1[u], str + "r ", u + 1);// 放在右边。
}

int main() {
    while (cin >> n) {
        for (int i = 0; i < n; i ++) {
            cin >> s1 >> s2;

            res.clear();
            dfs("", "", 0);
            cout << '{' << endl;
            for (int i = 0; i < res.size(); i ++) {
                cout  << res[i] << endl;
            }
            cout << '}' << endl;
        }
    }
    return 0;
}