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;
}
网友评论