（课设第一套）1-4 消息传递接口 (100 分)（模拟：线程）

题目

1-4 消息传递接口 (100 分)
老师给了 T 份 MPI 的样例代码，每份代码都实现了 n 个进程通信。这些进程标号从 0 到 n − 1，每个进程会顺序执行自己的收发指令，如：“S x”，“R x”。“S x”表示向x 号进程发送数据，“R x”表示从 x 号进程接收数据。每一对收发命令必须匹配执行才能生效，否则会“死锁”。 举个例子，x 号进程先执行发送命令“S y”，y 号进程必. 须. 执行接送命令“R x”，这一对命令才执行成功。否则 x 号进程会一直等待 y 号进程执行对应的接收命令。反之，若 y 号进程先执行接收命令“R x”，则会一直等待 x 号进程执行发送命令“S y”，若 x号进程一直未执行发送命令“S y”，则 y 号进程会一直等待 x 号进程执行对应的发送命令。上述这样发送接收命令不匹配的情况都会造成整个程序出现“死锁”。另外，x 号进程不会执行“S x”或“R x”，即不会从自己的进程收发消息。.现在老师请你判断每份样例代码是否会出现“死锁”的情况。每个进程的指令最少有 1 条，最多有 8 条，这些指令按顺序执行，即第一条执行完毕，才能执行第二条，依次到最后一条。

输入格式:
从标准输入读入数据。 输入第一行两个正整数 T, n，表示有 T 份样例代码，实现了 n 个进程通信。 接下来有 T × n 行，每行有若干个（1 − 8 个）字符串，相邻之间有一个空格隔开，表示相应进程的收发指令。不存在非法指令。对于第 2 + i, 0 ≤ i ≤ (T × n − 1) 行，表示第 i ÷ n（商）份代码的 i KQ/ n（余数）号进程的收发指令。 （比如，“S1”表示向 1 号进程发送消息，“R1”表示从 1 号进程接收消息。细节请参考样例。）

输出格式:
输出到标准输出。 输出共 T 行，每行一个数字，表示对应样例代码是否出现“死锁”的情况。1 表示死锁，0 表示不死锁。

输入样例:
3 2
R1 S1
S0 R0
R1 S1
R0 S0
R1 R1 R1 R1 S1 S1 S1 S1
S0 S0 S0 S0 R0 R0 R0 R0
输出样例:
0
1
0
作者
景荣
单位
燕山大学
代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB

思路

模拟题

参考的别人的思路

因为涉及到某个线程的删除和添加

用list删除效率比较高

代码

//不存在非法指令
//x号进程不会执行S x
//顺序执行
//指令最少一条 最多八条
//输入格式 i KQ/ n（余数）号
using namespace std;
#include<unordered_set>
#include<bits/stdc++.h>
int main() {
    
	int t, n;
	cin >> t >> n;
	getchar();
	for (int z = 0; z < t; z++) {
    //t份代码
		unordered_set<int>waiting;//等待中 
		list < pair<queue<int>, int>>pool;//线程池
		for (int i = 0; i < n; i++) {
    //n个线程
			pool.push_back({
     queue<int>(),INT_MAX });//为新线程腾地
			string temp;//一整行指令
			getline(cin, temp);//每个线程对应一串指令
			//拆分指令
			//只有一个指令的情况下，最终没有空格
			for (int j = 0,c; j < temp.size(); j = c + 1) {
    
				c = temp.find(" ", j);
				if (c== string::npos) {
    
					c = temp.size();
				}
				if (temp[j] == 'S') {
    //发送
					pool.back().first.push(i*10000+stoi(string(temp.begin() + j + 1, temp.begin() + c)));//范围可能会
				}
				else {
    //接受
					pool.back().first.push(-i - 10000*stoi(string(temp.begin() + j + 1, temp.begin() + c)));//范围可能会错
				}
			}
		}
		bool flag = true;
		while (flag && !pool.empty()) {
    //池中还有
			for (auto i = pool.begin(); i != pool.end(); i++) {
    //一趟至少有一对匹配，否则锁死
				if (waiting.find(i->second) != waiting.end()) {
    //该进程阻塞，下一个
					continue;
				}//注意前两次if的顺序
				else if ((i->first).empty()) {
    //该进程没有可以继续执行的指令
					i->second = 0;
					continue;
				}
				else {
    
					while (!(i->first).empty()) {
    //指令非空，就出队，直到未找到匹配的或指令没了
						int getout =( i->first).front();
						(i->first).pop();
						if (waiting.find(-getout) != waiting.end()) {
    //找到匹配的
							waiting.erase(-getout);
							flag = false;
						}
						else {
    
							i->second = getout;
							waiting.insert(getout);
							break;
						}
					}				
				}
			}
			if (flag == true)break;
			else flag = true;
		}
		bool pass = true;
		if (waiting.empty()) {
    
			for (auto i = pool.begin(); i != pool.end(); i++) {
    
				if (i->second != 0) {
    
					pass = false;
					break;
				}
			}
		}
		else pass = false;
		if (pass)cout << "0" << endl;
		else cout << "1" << endl;
	}
	return 0;
}