2021内蒙古自治区第十六届“华讯杯”大学生程序设计竞赛---- 将军棋

这天Alice和Bob在玩一个经典的棋盘游戏——将军棋。 由于将军棋的规则比较复杂，他们决定玩简化版的将军棋，简化后的规则如下：

1. 游戏开始在一个N*M的地图上，每个格子的位置由(x,y),x∈[1,N],y∈[1,M]表示。每个格子可以驻扎一些小兵。
2. 开始前Alice和Bob各占据一个格子，称为各自的城堡。城堡开始时有若干个小兵。初始时地图上除了各自的城堡所在的格子，都为空（即没有任何一方的小兵）。
3. 游戏有Q个回合，每个回合每人行动一次，每回合都是Alice先行动。在每个回合中，当前行动的人必须选择一个格子并命令该格子里的小兵移动，这个格子必须满足：

• 格子里有兵，且数量大于1
• 格子里的兵属于当前行动者的阵营

1. 选定格子后，当前行动的人还需选择一个方向（上下左右中的一个），然后留下且仅留下一个小兵在选定的格子里，其余的小兵都移动到对应方向的相邻格子里（以下称为目标格子）。当然，目标格子必须在棋盘内。
2. 此时有三种情况：

• 若目标格子为空：移动的兵力直接进入目标格子，数量不变
• 若目标格子不为空且目标格子里的兵力和行动者属于同一阵营：两批兵力合并，数量相加
• 若目标格子不为空且目标格子里的兵力和行动者不属于同一阵营：此时两批兵力会发生战斗 Ⅰ.若两批兵力数目相同，则他们会同归于尽，即战斗后目标格子会变成空 Ⅱ.若目标格子里的兵力数量更多，则移动的兵力会全部死亡，而目标格子里的兵力数量会减少移动的兵力数量。 Ⅲ.若移动的兵力数量较多，则目标格子的兵力会全部死亡，移动的兵力会减少目标格子的兵力数量，然后进驻目标格子

1. 每个人在行动开始前，她的城堡里将会多出一个兵的数量，这样就能保证一定可以行动。
2. 如果在任意一次行动后，一个阵营的城堡里被对方阵营进驻（或者变为空），该阵营输掉比赛，另一方赢得比赛。此时比赛结束， 后面的回合就不用执行了。
3. 现在已知双方所有的行动，要求输出游戏结果。
4. 若Alice获胜，输出"Alice wins!!!"，反之输出"Bob wins!!"（均不含引号）
5. 若Q个回合后仍无人获胜，视为平局，输出"draw!"
6. 输出获胜结果后，换行输出两个整数，分别代表Alice和Bob的分数。一方的分数即地图上所有属于她的兵力的和。 具体见样例和样例解释（有图片解释）

输入格式：

第一行一个正整数T（T<=10），表示数据组数 对于每组数据： 第一行两个正整数N，M（1<=N,M<=400） 接下来一行三个正整数xa​,ya​,cnta​，表示Alice城堡的坐标(xa​,ya​)和初始的小兵数量 接下来一行三个正整数xb​,yb​,cntb​，表示Bob城堡的坐标(xb​,yb​)和初始的小兵数量，保证cnta​,cntb​>1 接下来一个正整数Q（1<=Q<=100000），表示总回合数 接下来Q*2行，表示每个回合的行动 对于每个回合，输出两行，第一行表示Alice的行动，第二行表示Bob的行动 每次行动用两个正整数和一个字符表示，字符只属于{U,D,L,R}，表示上下左右的四个方向 例如"3 3 U"表示将(3,3)的格子向上移动（保证行动一定合法，即当前格子属于行动方且兵数>1）

输出格式：

对于每组测试数据： 第一行输出“Alice wins!!!”，“Bob wins!!”，“draw!"中的一个，表示游戏结果 第二行输出两个整数，分别表示Alice和Bob的分数

输入样例：

1
3 3
1 1 6
3 3 13
4
1 1 R
3 3 L
1 2 D
3 2 U
1 1 R
2 2 U
1 1 D
1 2 L

输出样例：

Bob wins!!
1 8

#include <bits/stdc++.h>
using namespace std;struct in
{int num;int who;
}q[405][405];int t,n,m,x1,y_1,x2,y2;///Alice为1;
///Bob为2;
int fun(int x,int y,char d,int who)
{int newx=x;int newy=y;if(d=='U')newx--;else if(d=='D')newx++;else if(d=='L')newy--;else if(d=='R')newy++;if(q[newx][newy].num==0){int temp=0;///记录每一步应该走几个兵；temp=q[x][y].num-1;q[x][y].num=1;q[newx][newy].num=temp;q[newx][newy].who=who;}else{///该目标位置有兵，判断是否是己方阵营///如果是己方阵营；if(q[newx][newy].who==who){int temp=q[x][y].num-1;q[newx][newy].num=temp+q[newx][newy].num;q[x][y].num=1;}else{///如果不是己方阵营///如果兵力大于目标兵力，则可以覆盖；if(q[newx][newy].num-(q[x][y].num-1)<0){int temp=q[x][y].num-1;q[newx][newy].num=temp-q[newx][newy].num;q[x][y].num=1;if(q[newx][newy].who==1)q[newx][newy].who=2;elseq[newx][newy].who=1;}else if(q[newx][newy].num-(q[x][y].num-1)>0){int temp=q[x][y].num-1;q[newx][newy].num=q[newx][newy].num-temp;q[x][y].num=1;}else if(q[newx][newy].num-(q[x][y].num-1)==0){q[newx][newy].num=0;q[x][y].num=1;q[newx][newy].who=0;}}}if(q[x1][y_1].num==0||q[x1][y_1].who==2)return 1;else if(q[x2][y2].num==0||q[x2][y2].who==1)return 2;elsereturn 0;
}int main()
{cin>>t;while(t--){cin>>n>>m;cin>>x1>>y_1;cin>>q[x1][y_1].num;q[x1][y_1].who=1;cin>>x2>>y2;cin>>q[x2][y2].num;q[x2][y2].who=2;int w;cin>>w;w*=2;int e=1;///每一回合该阵营会加一个兵；int mark=0;while(w--){int x,y;char d;cin>>x>>y>>d;if(mark>0)continue;if(e%2==1){q[x1][y_1].num+=1;mark=fun(x,y,d,1);}else{q[x2][y2].num+=1;mark=fun(x,y,d,2);}e++;}int cnt1=0,cnt2=0;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(q[i][j].who==1)cnt1+=q[i][j].num;else if(q[i][j].who==2)cnt2+=q[i][j].num;}}if(q[x1][y_1].who==1&&q[x2][y2].who==2)cout<<"draw!"<<endl;else if( (q[x1][y_1].who==2&&q[x2][y2].who==2) ||q[x1][y_1].num==0||mark==1 )cout<<"Bob wins!!"<<endl;else if((q[x1][y_1].who==1&&q[x2][y2].who==1) ||q[x2][y2].num==0 ||mark==2 )cout<<"Alice wins!!!"<<endl;cout<<cnt1<<" "<<cnt2<<endl;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)q[i][j].who=q[i][j].num=0;}return 0;
}