(the first set of course design) 1-4 message passing interface (100 points) (simulation: thread)

subject

1-4 Messaging interface (100 branch )
The teacher gave it T Share MPI Sample code for , Each code implements n Process communication . These processes are labeled from 0 To n − 1, Each process will execute its own send and receive instructions in sequence , Such as ：“S x”,“R x”.“S x” To express to x Send data to process No ,“R x” From x No. process receives data . Each pair of send / receive commands must be executed to take effect , Otherwise “ Deadlock ”. for instance ,x Process No. 1 executes the send command first “S y”,y No. process must . Must be . Execute the transfer command “R x”, This pair of commands were successfully executed . otherwise x No. process will be waiting y No. process executes the corresponding receive command . conversely , if y Process No. 1 executes the receive command first “R x”, Will wait x No. process executes the send command “S y”, if x No. process has not executed the send command “S y”, be y No. process will be waiting x No. process executes the corresponding send command . The mismatching of the above sending and receiving commands will cause the whole program to appear “ Deadlock ”. in addition ,x No. process will not execute “S x” or “R x”, That is, they will not send or receive messages from their own processes .. Now the teacher asks you to judge whether each sample code will appear “ Deadlock ” The situation of . Each process has at least 1 strip , At most 8 strip , These instructions are executed sequentially , That is, the execution of Article 1 is completed , To implement Article 2 , Go to the last one .

Input format :
Reading data from standard input . Enter two positive integers on the first line T, n, Express T Sample code , Realized n Process communication . Next there is T × n That's ok , There are several in each line （1 − 8 individual ） character string , There is a space between the adjacent , Indicates the receiving and sending instructions of the corresponding process . There are no illegal instructions . For the first 2 + i, 0 ≤ i ≤ (T × n − 1) That's ok , It means the first one i ÷ n（ merchant ） Of the code i KQ/ n（ remainder ） Send and receive instructions for process No . （ such as ,“S1” To express to 1 Send message to process No ,“R1” From 1 Message received by process No . Please refer to the example for details .）

Output format :
Output to standard output . The output, T That's ok , One number per line , Indicates whether the corresponding sample code appears “ Deadlock ” The situation of .1 Indicates deadlock ,0 It means no dead lock .

sample input :
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
sample output :
0
1
0
author
Jingrong
Company
Yanshan University
Code length limit
16 KB
The time limit
400 ms
Memory limit
64 MB

Ideas

Simulation question

Refer to others' ideas

Because it involves the deletion and addition of a thread

use list Delete is more efficient

Code

// There are no illegal instructions 
//x No. process will not execute S x
// Sequential execution 
// At least one instruction   Up to eight 
// Input format  i KQ/ n（ remainder ） Number 
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 Copy code 
		unordered_set<int>waiting;// Waiting for the  
		list < pair<queue<int>, int>>pool;// Thread pool 
		for (int i = 0; i < n; i++) {
    //n Threads 
			pool.push_back({
     queue<int>(),INT_MAX });// Make room for new threads 
			string temp;// A whole line of instructions 
			getline(cin, temp);// Each thread corresponds to a string of instructions 
			// Split instruction 
			// When there is only one instruction , Finally, there are no spaces 
			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') {
    // send out 
					pool.back().first.push(i*10000+stoi(string(temp.begin() + j + 1, temp.begin() + c)));// The scope may 
				}
				else {
    // Accept 
					pool.back().first.push(-i - 10000*stoi(string(temp.begin() + j + 1, temp.begin() + c)));// The scope may be wrong 
				}
			}
		}
		bool flag = true;
		while (flag && !pool.empty()) {
    // There are still 
			for (auto i = pool.begin(); i != pool.end(); i++) {
    // There is at least one match in a trip , Otherwise, it will be locked 
				if (waiting.find(i->second) != waiting.end()) {
    // The process is blocking , next 
					continue;
				}// Pay attention to the first two if The order of 
				else if ((i->first).empty()) {
    // The process has no instructions to continue 
					i->second = 0;
					continue;
				}
				else {
    
					while (!(i->first).empty()) {
    // The instruction is not empty , Just out of the team , Until no match is found or the instruction is gone 
						int getout =( i->first).front();
						(i->first).pop();
						if (waiting.find(-getout) != waiting.end()) {
    // Find a match 
							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;
}