题目如上:
我的代码如下:
#include<bits/stdc++.h>
using namespace std;
int T, n;
struct node {
int flag; // 0:S 1:R
int num;
// 将str的信息转换为flag和num;
node(string str) {
flag = str[0] == 'S' ? 0 : 1;
stringstream s;
s << str.substr(1, str.size() - 1);
s >> num;
}
};
queue<node> q[10005]; // 存放进程的信息
// 清空q,不知道内存会不会炸
void clear() {
queue<node> qq[10005];
swap(q, qq);
}
int main() {
cin.sync_with_stdio(false);
cin >> T >> n;
getchar(); // 整数和字符串之间的回车一般还是需要专门的getchar处理的;
// T组数据
for (int i = 0; i < T; i++) {
clear();
for (int j = 0; j < n; j++) {
string input;
getline(cin,input); // 读入字符串;
int pos=input.find(' ');
while (pos != input.npos) {
q[j].push(node(input.substr(0, pos)));
input.erase(0, pos+1);
pos = input.find(' ');
}
q[j].push(node(input.substr(0, 2)));
}
bool flag = false; // 判断一轮是否进行处理
bool is_empty = true; // 判断是否全员是空队列
// 上面优化估计有点难,看下面如何优化
while (true) {
flag = false;
is_empty = true;
for (int j = 0; j < n; j++) {
if (!q[j].empty()) {
is_empty = false;
// 考虑S
if (q[j].front().flag == 0) {
int purpose = q[j].front().num;
// 剪枝;
if (q[purpose].empty()) {
flag = false;
break;
}
// 如果恰好符合要求;
else if ((q[purpose].front().flag == 1) && (q[purpose].front().num == j)) {
q[purpose].pop();
q[j--].pop();
flag = true;
}
}
}
}
// 全为空; 或者没有操作
if (is_empty || !flag) {
break;
}
}
if (is_empty) {
cout << 0 << endl;
}
else if (!flag) {
cout << 1 << endl;
}
}
}
测试用例文字版:
测试用例:
3 2
R1 S1
S0 R0
R1 S1
R0 S0
R1 R1 R1 S1 S1 S1 S1
S0 S0 S0 R0 R0 R0 R02 3
R1 S1
R2 S0 R0 S2
S1 R1
R1
R2 S0 R0
S1 R1
希望有大佬帮忙解决下