CCF 消息传递接口 60分

我会带着你远行 2023-05-28 15:56 30阅读 0赞

大家不要看，我就是写个博客让别人给我找找错误。

#include<bits/stdc++.h>
    #include<vector>
    #include<queue>
    using namespace std;
    const int MAXN = 10005;
    
    /*
    ** 指令 
    */
    struct Command{
    	int process; //哪个进程的指令 
    	char type; //指令类型（例如：S2中的S，R3中的R）。 
    	int pid;   //指令对应的数字（例如：S2中的2，R3中的3）。 
    	Command(int process,char type,char pid){
    		this->process = process;
    		this->type = type;
    		this->pid = pid - '0';
    	}
    };
    queue<Command> source[MAXN];  //进程的待处理指令集（包括R指令和S指令）。 
    
    /*
    ** 处理R指令 
    ** 参数：
    **		num: 哪个进程的R指令 
    **      recIndex : R指令对应的进程编号
    **      例如：3号进程执行R2指令，其中num=3,recIndex=2。 
    */
    bool dealR(int num,int recIndex){
    	/*
    	** 查看recIndex对应的进程的第一条指令是不是:Snum (num是一个数字)。  
    	** 举例：1号进程现在的指令是R2，那我就看看2号进程的第一条指令是不是S1。 
    	*/
    	if(source[recIndex].empty()){
    		return false; //匹配失败 
    	}
    	Command command = source[recIndex].front();
    	if(command.type == 'S' && command.pid == num){
    		source[recIndex].pop();
    		return true; //S指令和R指令匹配成功。 
    	}else{
    		return false; //匹配失败。 
    	}
    } 
    
    /*
    ** 处理S指令 
    ** 参数：
    **     sendNum: S指令的发送方
    **     recNum:  S指令的接收方
    **     例如：1号进程发送S3指令，其中sendNum=1,recNum=3。 
    */
    bool dealS(int sendNum,int recNum){
    	/*
    	** 查看接收方(recNum)的当前指令是不是 : RsendNum (sendNum是个数字)
    	** 举例：1号进程现在的指令是S2，那我就看看2号进程的第一条指令是不是R1。 
    	*/
    	if(source[recNum].empty()){
    		return false; //匹配失败 
    	}
    	Command command = source[recNum].front();
    	if(command.type == 'R' && command.pid == sendNum){
    		source[recNum].pop();
    		return true; //S指令和R指令匹配成功。 
    	}else{
    		return false; //匹配失败。 
    	}
    }
    
    /*
    ** 判断各个进程的待处理指令集是不是空了 
    */
    bool judgeEmpty(int n){
    	for(int i=0;i<n;i++){
    		if(!source[i].empty()){
    			return false;  //不空 
    		}
    	} 
    	return true; 
    }
    
    /*
    ** 处理各个进程的当前指令
    ** 当前指令指的是source[u]的队首元素。 1<=u<=n 
    */ 
    bool dealNowCommand(int n){
    	bool flag;   
    	bool isSuccess;  //指令是否执行成功 
    	while(true){
    		flag = false;  //初始化 (flag表示当前这次for循环，有没有哪条指令执行成功了)
    		for(int i=0;i<n;i++){
    			isSuccess = false; //初始化 
    			if(source[i].empty()){
    				continue;
    			}
    			Command command = source[i].front();
    			if(command.type == 'S'){
    				if(command.process == command.pid){ //是不是给本进程发送了一个S指令 
    					return false;
    				}
    				//执行S指令 
    				isSuccess = dealS(command.process,command.pid); //指令执行成功 
    			}else{
    				if(command.process == command.pid){ //是不是给本进程发送了一个R指令 
    					return false;
    				}
    			}
    			//刚才那条指令执行成功了。 
    			if(isSuccess){
    				source[i].pop(); //从待处理指令集中删除刚才执行成功的那条指令 
    				flag = true; //这次for循环中有一个指令执行成功了。 
    			}
    		}
    		//如果source空了，说明没有死锁。	
    		if(judgeEmpty(n)){
    			return true;
    		}
    		//如果这次for循环没有一个指令执行成功，那么死锁发生。 
    		if(!flag){ 
    			return false; 
    		}	
    	}
    	return true;
    } 
    
    /*
    ** 处理源数据
    ** 参数：
    **     num: 进程编号
    **     str: 输入的一行数据，如：R1 R1 R1 R1 S1 S1 S1 S1
    */
    void dealSource(int num,string input){
    	int u,v;
    	string temp;
    	for(int i=0;i<input.size();i=u+1){
    		u = input.find(" ",i);
    		if(u == string::npos){
    			u = input.size();
    		}
    		temp = input.substr(i,u-i);
    		source[num].push(Command(num,temp[0],temp[1]));
    	}
    }
    
    /*
    ** 清空未处理的源数据。 
    */
    void destroyData(int n){
    	for(int i=0;i<=n;i++){
    		while(!source[i].empty()){
    			source[i].pop();
    		}
    	}
    }
     
    int main(){
    	int t,n;
    	string input;
    	cin>>t>>n;
    	getchar();
    	while(t--){
    		for(int i=0;i<n;i++){
    			getline(cin,input);
    			dealSource(i,input); //字符串分割 
    		}
    		bool ans = dealNowCommand(n);
    		if(ans){
    			cout<<"0"<<endl;
    		}else{
    			cout<<"1"<<endl;
    		}
    		destroyData(n); //重置变量 
    	}
    	return 0; 
    }