P2482 [SDOI2010] 猪国杀

#include<bits/stdc++.h>
using namespace std;

int seat[30];//由于无懈，南蛮等牌的需求，方便从每一名玩家开始向逆时针遍历所有玩家 
int n,m;
int king;//主公的编号 
int fnum;//反贼的数量 
bool lei[15];//类反贼标记 
int identity[15];//身份 
int predict[15];//别人对他身份的推测（即是否跳了身份，若跳了则是身份，没跳则是0） 
queue<char> card;//摸牌堆 
vector<char> player[15];//每名玩家的手牌 
bool dead[15];//是否死亡 
int hp[15];//血量 
int dis[15];//根据题意，对于每名玩家，只会有一名其他玩家与他距离为1，dis[i]即表示与i距离为1的那位玩家 
bool Klimit;//出杀限制，若当前回合出过杀则为1否则为0，每一个新回合更新为0 
bool equip[15];//是否装备了诸葛连弩 
int gameover;//游戏是否结束，没结束则为0，主公胜利则为1，反贼胜利则为2 

void update_dis()//更新距离 
{
	for(int i=1;i<=n;i++)
	{
		int tt=i+1;
		while(dead[seat[tt]]==1)
		{
			tt++;
		}
		dis[i]=seat[tt];
	}
}

void get_card(int p,int cnt)//让玩家p从牌堆中摸cnt张牌 
{
	for(int i=1;i<=cnt;i++)
	{
		player[p].push_back(card.front());
		if(card.size()!=1)
			card.pop();
	}
}

void dying(int from,int p)//当玩家p进入濒死状态时，伤害源时from，
{
	//判断玩家p是否有桃 
	bool flag=0;
	for(int i=0;i<player[p].size();i++) 
	{
		if(player[p][i]=='P')
		{
			player[p].erase(player[p].begin()+i);
			flag=1;
			break;
		}
	}
	if(flag==1)
		hp[p]++;
	else//没有桃，那就处理后事（ 
	{
		dead[p]=1;//玩家p死亡 
		if(p==king)//如果是主公那么游戏结束 
		{
			gameover=2;
			return;
		}
		
		if(identity[p]==2)//如果是反贼 
		{
			fnum--;//反贼数量-1 
			if(fnum==0)//如果反贼都没了那么游戏结束 
			{
				gameover=1;
				return;//！！！如果这里不结束那么会导致伤害源多摸三张牌，输出时伤害源的手牌会多三张牌！！！ 
			}
			get_card(from,3);//伤害源摸3张牌 
		}
		
		if(identity[p]==1 && from==king)//如果玩家p是忠臣并且伤害源是主公 
		{
			player[king].clear();//清空手牌 
			equip[king]=0;//！！！装备栏也要清空！！！ 
		}
		
		update_dis();//每有玩家死亡就更新距离 
	}
}
//无懈可击 
int J(int from,int to,int k)//玩家from向玩家to打出一张锦囊牌，其中锦囊牌对玩家to的性质是k（k为0表示表敌意，k为1表示献殷勤） 
{ 
	//我们要寻找是否有玩家会为这张锦囊牌打出无懈可击，如果打出无懈可击且生效了返回1，否则返回0 
	//性质：predict[to]不为0（没人会给没亮身份的玩家出无懈可击，包括他自己） 
	for(int i=from;i<n+from;i++)//逆时针遍历所有玩家 
	{
		if(dead[seat[i]])continue;//如果死亡就跳过 
		int x=seat[i]; 
		if(identity[x]==predict[to] && k==0)//如果该玩家与玩家to同阵营而且这张锦囊牌对玩家to产生不好的影响 
		{
			for(int j=0;j<player[x].size();j++)//寻找无懈可击 
			{
				if(player[x][j]=='J')//找到了 
				{
					player[x].erase(player[x].begin()+j);
					predict[x]=identity[x];//玩家x跳身份了 
					if(J(x,to,1))//无懈可击也是锦囊牌，判断是否有玩家y无懈这张无懈可击且y的无懈可击生效了 
						return 0;//如果y的无懈可击生效了，这张就无效了 
					else 
						return 1;//否则这张就生效了 
				}
			}
		}
		else if(identity[x]+predict[to]==3 && k==1)//如果x与to身份不同且这张锦囊牌将有利于to 
		{
			for(int j=0;j<player[x].size();j++)//和上面部分同理 
			{
				if(player[x][j]=='J')
				{
					player[x].erase(player[x].begin()+j);
					predict[x]=identity[x];
					if(J(x,to,0))
						return 0;
					else 
						return 1;
				}
			}
		}
	}
	return 0;//没人有无懈可击 
}

//南蛮入侵 
void N(int from,int to)//from打出的南蛮此时正在对to生效 
{
	if(J(from,to,0))//有人无懈吗? 
	{
		return;//有人无懈了 
	}
	
	bool flag=0;
	for(int i=0;i<player[to].size();i++)//to有杀吗? 
	{
		if(player[to][i]=='K')
		{
			player[to].erase(player[to].begin()+i);
			flag=1;//to有杀 
			break;
		}
	}
	if(flag==0)hp[to]--;//to没有杀,掉血了 
	if(hp[to]==0)//如果没血了怎么办? 
	{
		dying(from,to);//猎杀时刻 
	}
	if(flag==0 && to==king && predict[from]==0)//如果to是主公并且南蛮让他掉血了 
	{
		lei[from]=1;//主公认为from是类反贼 
	}
}

//万箭齐发 
void W(int from,int to)//与上面同理 
{	
	if(J(from,to,0))
	{
		return;
	}
	
	bool flag=0;
	for(int i=0;i<player[to].size();i++)
	{
		if(player[to][i]=='D')//把杀换成闪 
		{
			player[to].erase(player[to].begin()+i);
			flag=1;
			break;
		}
	}
	if(flag==0)hp[to]--;
	if(hp[to]==0)
	{
		dying(from,to);
	}
	if(flag==0 && to==king && predict[from]==0)
	{
		lei[from]=1;
	}
}

//决斗 
void F(int from,int to)//from对to决斗 
{
	if(from!=king)//如果from不是主公,只有主公才会对同阵营的人决斗 
		predict[from]=3-predict[to];//from的阵营与to相反(因为只有亮身份的人才会被决斗,predict[to]一定有值) 
	if(J(from,to,0))return;//无懈可击判断 
	
	if(from==king && identity[to]==1)//如果发起人是主公,目标是忠臣,忠臣不会出杀稳定掉一血(忠臣不会反过来决斗主公,而且这里是identity不是predict) 
	{
		hp[to]--;
		if(hp[to]==0)
			dying(from,to);//濒死 
		return;
	}
	
	bool flag1,flag2;
	while(1)
	{
		flag1=0;
		for(int i=0;i<player[to].size();i++)//to有杀吗 
		{
			if(player[to][i]=='K') 
			{
				player[to].erase(player[to].begin()+i);
				flag1=1;//有了 
				break;
			}
		}
		if(flag1==0)//没有 
		{
			hp[to]--;
			if(hp[to]==0)
				dying(from,to);
			break;
		}
		
		flag2=0;
		for(int i=0;i<player[from].size();i++)//from有杀吗 
		{
			if(player[from][i]=='K')
			{
				player[from].erase(player[from].begin()+i);
				flag2=1;//有了 
				break;
			}
		}
		if(flag2==0)//没有 
		{
			hp[from]--;
			if(hp[from]==0)
				dying(to,from);
			break;
		}
	}
}

//杀 
void K(int from,int to)//from对to出杀 
{
	if(from!=king)//from亮身份 
		predict[from]=3-predict[to];
	bool flag=0;
	for(int i=0;i<player[to].size();i++)//to有闪吗 
	{
		if(player[to][i]=='D')//有了 
		{
			player[to].erase(player[to].begin()+i);
			flag=1;
			break;
		}
	}
	if(flag==0)hp[to]--;//没有 
	if(hp[to]==0)
	{
		dying(from,to);//濒死 
	}
}

int rounduse(int p,int x)//玩家p"尝试"打出他的第x+1张牌,即player[p][x] ,打出了返回1,否则返回0 
{
	switch(player[p][x])
	{
		case 'P'://桃 
			if(hp[p]<4)//没满血就用 
			{
				player[p].erase(player[p].begin()+x);
				hp[p]++;
				return 1;
			}
			else//满血了不出 
				return 0;
		case 'D'://闪(永远出不了) 
			return 0;
		case 'K'://杀(自己唯一能杀到的那个人是敌人吗) 
			if( (identity[p]+predict[dis[p]]==3 ||  (p==king && lei[dis[p]]==1 && predict[dis[p]]==0 /*类反贼的标记只有在没亮身份才有用*/) ) && (Klimit==0 || equip[p]==1/*诸葛连弩?*/))
			{
				Klimit=1;//出杀限制 
				player[p].erase(player[p].begin()+x);
				K(p,dis[p]);
				return 1;
			}
			else
				return 0;
		case 'F'://决斗 
			if(identity[p]==2)//如果p是反,题目设定他会尽可能去打主 
			{
				player[p].erase(player[p].begin()+x);
				F(p,king);
				return 1;
			}
			for(int i=p+1;i<n+p;i++)//逆时针找到第一个敌人 
			{
				if(identity[p]+predict[seat[i]]==3 || (p==king && lei[seat[i]]==1 && predict[seat[i]]==0) )
				{
					if(dead[seat[i]])continue;
					player[p].erase(player[p].begin()+x);
					F(p,seat[i]);
					return 1;
					break;
				}
			}
			return 0;
		case 'N'://南蛮入侵 
			player[p].erase(player[p].begin()+x);
			for(int i=p+1;i<n+p;i++)//逆时针遍历,每个人都会被打到 
			{
				if(dead[seat[i]])continue;
				N(p,seat[i]);
				if(gameover)return 1;//!!!注意如果南蛮在执行过程中游戏结束,那么必须让南蛮停止生效!!! 
			}
			return 1;
		case 'W'://万箭齐发,与南蛮同理 
			player[p].erase(player[p].begin()+x);
			for(int i=p+1;i<n+p;i++)
			{
				if(dead[seat[i]])continue;
				W(p,seat[i]);
				if(gameover)return 1;
			}
			return 1;
		case 'J'://无懈可击不能主动打出 
			return 0;
		case 'Z'://诸葛连弩直接无脑装
			player[p].erase(player[p].begin()+x);
			equip[p]=1;
			return 1;
	}
}

void round(int p)//玩家p的回合 
{
	Klimit=0;//更新出杀限制 
	if(dead[p])return;//如果死了那就没事了 
	
	get_card(p,2);//摸牌阶段 
	
	//从最左边开始搜索手牌,如果不能出就看下一张,如果打出了就从头搜索 
	int k=-1;
	while(1)
	{
		k++;
		if(k==player[p].size())break;
		if(rounduse(p,k))
		{
			k=-1;
		}
		if(dead[p])return;//!!!注意:如果在出牌过程中玩家打出决斗把自己整死了之后要停止出牌!!! 
		if(gameover)return;//游戏结束了也要停止出牌 
	}
}

int main()
{
	cin>>n>>m;
	
	for(int i=1;i<=n;i++)//初始化 
	{
		seat[i]=seat[n+i]=i;
	}
	
	string s;char c;
	for(int i=1;i<=n;i++)//1表示主忠阵营 2表示反贼阵营 
	{
		hp[i]=4;
		cin>>s;
		if(s[0]=='M')identity[i]=1,king=i;
		else if(s[0]=='Z')identity[i]=1;
		else if(s[0]=='F')identity[i]=2,fnum++;
		for(int j=1;j<=4;j++)//初始四张牌 
		{
			cin>>c;
			player[i].push_back(c);
		}
	}
	for(int i=1;i<=m;i++)//摸牌堆 
	{
		cin>>c;
		card.push(c);
	}
	predict[king]=1;//!!!注意:主公的身份是公布的!!! 
	update_dis();//更新距离 
	
	int tot=0;
	while(1)//开始回合循环 
	{
		tot++;
		if(tot==n+1)tot=1;
		round(tot);
		if(gameover)break;
	}
	if(gameover==1)//输出即可 
	{
		cout<<"MP\n";
	}
	else 
		cout<<"FP\n";
	for(int i=1;i<=n;i++)
	{
		if(dead[i])
		{
			cout<<"DEAD\n";
			continue;
		}
		for(int j=0;j<player[i].size();j++)
		{
			cout<<player[i][j]<<" ";
		}
		cout<<"\n";
	}
}