AcWing 3160. 拉马车
原题链接
简单
作者:
咲张熊猫人
,
2021-01-25 01:40:21
,
所有人可见
,
阅读 723
队列,栈等基本数据结构的考察
代码 (里面用了句goto省事,有空再优化优化)
#include<iostream>
#include<cstring>
#include<queue>
#include<stack>
#include<string>
using namespace std;
int n;
string s1,s2;
int B[20]; // 用来记录此时出牌区的的每张牌是否在场
int check(char c) // 将对应的字符转化为B数组中的一个对应位置
{
if(c >= '0' && c <= '9') return c - '0';
switch (c)
{
case 'X':return 10;
case 'J':return 11;
case 'Q':return 12;
case 'K':return 13;
case 'A':return 14;
default: break;
}
return -1;
}
auto main() -> int
{
while(cin >> s1 >> s2) // 由于测试数据多组, 故这里采用这种写法
{
int ans = 0; // ans 为A,B两个玩家进行游戏的次数,若进行次数过多认为游戏无法结束,输出 -1
queue<char> q1, q2; // 由于手牌的打出和收回这个行为很像队列的操作,故定义两个队列用于保存卡牌信息
stack<char> st;
memset(B,0,sizeof(B)); // 将检测数组清空
for(auto c : s1)
q1.push(c); //将所有卡牌入队
for(auto c : s2)
q2.push(c);
while(q1.size() && q2.size()) // 当双方手牌都有剩余时,双方继续
{
auto c = q1.front(); // 首先由A方先出队
st.push(c), B[check(c)]++, q1.pop(); //将出队的元素入栈,然后检测该元素是否之前已经出现过且还在场上,然后pop完成出队操作。
while(B[check(c)] > 1) // 检测到当前打出的牌与场上有的牌相同,则进入循环依次将场上的牌按照后出先进的顺序出栈表示收回场上的牌,然后依次入队到对尾表示将赢得的手牌放到后面
{
while(B[check(c)] != 0) B[check(st.top())]--,q1.push(st.top()), st.pop();
c = q1.front(); // 因为赢牌的人再出一次牌,故入栈然后继续检测是否有赢牌
st.push(c), B[check(c)]++,q1.pop();
}
if(!q1.size()) break; // 如果此时A的手牌为空直接结束,因为A已经没有任何手段收回场上的牌,故B后面不用处理必赢
c = q2.front(); // 如A操作相同
st.push(c), B[check(c)]++, q2.pop();
while(B[check(c)] > 1)
{
while(B[check(c)] != 0) B[check(st.top())]--,q2.push(st.top()), st.pop();
c = q2.front();
st.push(c), B[check(c)]++, q2.pop();
}
if(ans > 1e+4) // 如果次数过多,认为游戏无法结束 , 直接goto跳出while和防止输出
{
cout << -1 << endl;
goto end;
}
ans++;
}
if(q1.size())
{
while(q1.size()) cout << q1.front(), q1.pop();
cout << endl;
}
if(q2.size())
{
while(q2.size()) cout << q2.front(), q2.pop();
cout << endl;
}
end:;
}
return 0;
}