CCF CSP 201903-4.消息传递接口

---

分析：

1.定义结构体类型Command

typedef struct Node {
	// 0表示发送S,1表示接收R
	int status;
	// 目标进程
	int target;
} Command;

2.处理输入

使用stringstream处理空格，得到各收发指令。每个进程的收发指令，使用queue<Command>存储；每份样例代码，使用vector<queue<Command> > arr存储。

3.执行模拟操作

执行如下循环：

遍历arr，若当前进程arr[i]不为空，此时，如果队首指令cmd的目标进程arr[cmd.target]为空，则循环结束，出现死锁；

否则，判断目标进程队首指令cmd2的状态与cmd的状态是否相符，以及cmd2的目标进程是否为当前进程，即cmd.status + cmd2.status == 1 && cmd2.target == i，

若上述条件满足，则对当前进程和目标进程执行出队操作，继续遍历当前进程的下一个指令。

当遍历arr，没有出队操作时，循环结束。

此时，若arr中任一进程不为空，则表示出现了死锁；否则，表示程序顺利执行。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <queue>
#include <string>
#include <sstream>
using namespace std;

typedef struct Node {
	// 0表示发送S,1表示接收R
	int status;
	// 目标进程
	int target;
} Command;

int main() {
	int t, n;
	cin >> t >> n;
	getchar();

	// 处理某份代码
	while (t--) {
		vector<queue<Command> > arr;
		string str;
		// 处理某个进程
		for (int i = 0; i < n; i++) {
			queue<Command> qu;
			getline(cin, str);
			stringstream ss;
			ss << str;
			while (ss >> str) {
				Command cmd;
				if (str[0] == 'S') {
					cmd.status = 0;
				} else {
					cmd.status = 1;
				}
				int num = atoi(str.substr(1, str.size()).c_str());
				cmd.target = num;
				qu.push(cmd);
			}
			arr.push_back(qu);
		}

		bool flag = true;
		while (flag) {
			flag = false;
			for (int i = 0; i < arr.size(); i++) {
				if (arr[i].empty()) {
					continue;
				}
				Command cmd = arr[i].front();
				if (arr[cmd.target].empty()) {
					flag = false;
					break;
				}
				Command cmd2 = arr[cmd.target].front();
				if (cmd.status + cmd2.status == 1 && cmd2.target == i) {
					arr[i].pop();
					arr[cmd.target].pop();
					i--;
					flag = true;
				}
			}
		}

		bool deadLock = false;
		for (int i = 0; i < arr.size(); i++) {
			if (!arr[i].empty()) {
				cout << 1 << endl;
				deadLock = true;
				break;
			}
		}
		if (!deadLock) {
			cout << 0 << endl;
		}
	}
	return 0;
}