《算法竞赛⼊门经典》习题4-1（象棋XiangqiACMICPCFuzhou2011，UV。。
。
原题及翻译
Xiangqi is one of the most popular two-player board games in China.
象棋是中国最流⾏的两⼈棋类游戏之⼀。
The game represents a battle between two armies with the goal of capturing the enemy’s “general” piece.
这个游戏代表了两军之间的⼀场战⽃，⽬的是⼲掉敌⼈的“将军”棋⼦。
In this problem, you are given a situation of later stage in the game.
在这个问题中，你会得到⼀个象棋残局。
Besides, the red side has already “delivered a check”.
另外，红⽅已经“将军”。
Your work is to check whether the situation is “checkmate”.
你的⼯作是检查情况是否是“将死”。
Now we introduce some basic rules of Xiangqi.
现在我们介绍⼀些象棋的基本规则。
Xiangqi is played on a 10×9 board and the pieces are placed on the intersections (points).
象棋在⼀块10×9的棋盘上演奏，棋⼦放在交叉点上。
The top left point is (1,1) and the bottom right point is (10,9).
左上点为（1,1），右下点为（10,9）。
There are two groups of pieces marked by black or red Chinese characters, belonging to the two players separately.
有两组⿊体字或红体字的棋⼦，分别属于两⼈的棋⼦。
During the game, each player in turn moves one piece from the point it occupies to another point.
在游戏过程中，每个玩家依次将⼀个棋⼦从它占据的点移 动到另⼀个点。
No two pieces can occupy the same point at the same time.
任何两个棋⼦都不能同时占据同⼀个点。
A piece can be moved onto a point occupied by an enemy piece, in which case the enemy piece is“captured” and removed from the board.
⼀个棋⼦可以移动到⼀个被敌⽅棋⼦占据的点上，在这种情况下，敌⽅棋⼦被“吃掉”并从棋盘上移除。
When the general is in danger of being captured by the enemy player on the enemy player’s next move, the enemy player is said to have “delivered a check”.
当将军在敌⽅玩家下⼀步⾏动中有被敌⽅玩家吃掉的危险时，就说敌⽅玩家已经“将军”。
If the general’s player can make no move to prevent the general’s capture by next enemy move, the situation is called “checkmate”.
如果将军的玩家不能采取任何⾏动来阻⽌将军被下⼀个敌⼈的⾏动俘虏，这种情况就称为“将死”。
We only use 4 kinds of pieces introducing as follows:
我们只使⽤以下4种材料：
General: the generals can move and capture one point either vertically or horizontally and cannot leave the “palace” unless the situation called “flying general” (see the figure above). “Flying general” means that one general can “fly” across the board to capture the enemy general if they stand on the same line without intervening pieces.
将/帅：将/帅可以垂直或⽔平移动并吃掉敌⽅的棋⼦，除⾮被称为“飞⾏将/帅（⽼将对脸）”（见上图），
否则不能离开“宫殿”。“飞⾏将/帅”是指如果⼀个将/帅站在同⼀条线上⽽中间⼜不隔着任何棋⼦的情况下，他就可以“飞”到敌⽅的将/帅处去吃掉敌⽅将/帅。
Chariot: the chariots can move and capture vertically and horizontally by any distance, but may not jump over intervening pieces
战车：战车可以任意距离垂直和⽔平移动和捕获，但不能跳过中间的棋⼦。
Cannon: the cannons move like the chariots, horizontally and vertically, but capture by jumping exactly one piece (whether it is friendly or enemy) over to its target.
加农炮：加农炮像战车⼀样⽔平和垂直移动，但通过跳到⽬标上（⽆论是友军还是敌⼈）来吃掉对⽅的棋⼦。
Horse: the horses have 8 kinds of jumps to move and capture shown in the left figure. However, if there is any pieces lying on a point away from the horse horizontally or vertically it cannot move or capture in that direction (see the figure below), which is called “hobbling the horse’s leg”.
马：如左图所⽰，马有8种跳跃动作和捕捉。然⽽，如果有任何棋⼦⽔平或垂直地躺在马的相邻点上，它就不能在该⽅向上移动（见下⾯的图），这被称为“马腿的蹒跚（蹩马腿）<；真亏百度敢翻译成这样
>”。
Now you are given a situation only containing a black general, a red general and several red chariots, cannons and horses, and the red side has delivered a check. Now it turns to black side’s move. Your job is to determine that whether this situation is “checkmate”.
现在你的处境只有⼀个将，⼀个帅和⼏辆红⾊战车，⼤炮和马匹，红⾊的⼀⽅已经将军了。现在轮到⿊棋的⾛棋了。你的⼯作是确定这种情况是将否被“将死”。
Input
The input contains no more than 40 test cases. For each test case, the first line contains three integers representing the number of red pieces （2 n 7) and the position of the black general. The following N lines contain details of N red pieces.
For each line, there are a char and two integers representing the type and position of the piece (type char ‘G’ for general,‘R’ for chariot, ‘H’ for horse and ‘C’ for cannon). We guarantee that the situation is legal and the red side has delivered the check.
There is a blank line between two test cases. The input ends by ‘0 0 0’.
输⼊
输⼊包含的测试⽤例不超过40个。对于每⼀个测试⽤例，第⼀⾏包含三个整数，表⽰红⾊块数n（2≤n≤7）和⿊⾊常规的位置。下⾯的n ⾏包含n个红⾊棋⼦的详细信息。对于每⼀⾏，有⼀个字符和两个整数表⽰棋⼦的类型和位置（类型char ‘G’表⽰将/帅，R’表⽰战
车，H’表⽰马，C’表⽰⼤炮）。我们保证这种情况是合法的，并且红⽅已经将军。两个测试⽤例之间有⼀个空⽩⾏。输⼊以“0 0 0”结尾。
Output
For each test case, if the situation is checkmate, output a single word ‘YES’, otherwise output the word ‘NO’.
Hint: In the first situation, the black general is checked by chariot and “flying general”. In the second situa- tion, the black general can move to (1, 4) or (1, 6) to stop check. See the figure on the right.
输出
对于每个测试⽤例，如果情况是“将死”，
则输出单个单词“yes”，否则输出单词“no”。
提⽰：
在第⼀种情况下，⿊将军由战车和“飞将军”检查。
在第⼆种情况下，⿊将军可以移动到
（1，4）或（1，6）停⽌检查。
请参见右侧的图。
Sample Input
样例输⼊
2 1 4
G 10 5
R 6 4
3 1 5
H 4 5
G 10 5
C 7 5
0 0 0
Sample Output
样例输出
YES NO
思路
1.象棋棋盘，⾸先想到建⽴⼀个⼆维数组，⽤来存储棋盘的每⼀个节点。
2.整体思路有两种（或者说我就能想到两种）：
第⼀种：遍历所有的红棋棋⼦，标记出红⽅的攻击范围，然后出⿊棋将军的移动范围，判断其移动范围是否是红棋攻击范围的⼦集，如果是，则“将死”；
第⼆种：先出⿊棋将军所有的移动范围，判断每⼀个移动后可能遭到的红⽅棋⼦威胁，如果所有的移动⽅案都不可⾏，则“将死”。
3.分类讨论的思想，不管是那种⽅案，都需要分情况讨论。
完整代码
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int CheckerboardR[11][10];//红棋盘
int CheckerboardB[11][10];//⿊棋盘
int red_number,Generalx,Generaly;
int red_number,Generalx,Generaly;
struct piece
{//声明棋⼦结构
char type;
int x;
int y;
};
void General_scope(int x,int y)
{//⿊棋将军的移动范围，利⽤20标识出来
if(x+1<=3) CheckerboardB[x+1][y]=20;
if(x-1>=1) CheckerboardB[x-1][y]=20;
if(y+1<=6) CheckerboardB[x][y+1]=20;
if(y-1>=4) CheckerboardB[x][y-1]=20;
}
int s_l_o_c_a_i_c(int x1,int y1,int x2,int y2)
{//判断两个棋⼦是否在同⼀⾏或同⼀列以及两个棋⼦之间是否有其它的棋⼦。if(x1==x2)
{//如果在同⼀⾏。
int flag=1;
for(int i=x1+1;i<x2;i++)
{//遍历从x1+1到x2的所以棋盘位置
if(CheckerboardR[x1][i]!=0)
{//如果有其它棋⼦
flag=0;
}
}
if(flag)
{//如果两个棋⼦在同⼀⾏并且之间没有其它的棋⼦，返回10。
return10;
}
else
{//如果两个棋⼦在同⼀⾏并且之间有其它的棋⼦，返回11。
return11;
}
}
else if(y1==y2)
{//如果在同⼀列。
int flag=1;
for(int i=y1+1;i<y2;i++)
{//遍历从y1+1到y2的所以棋盘位置
if(CheckerboardR[i][y1]!=0)
{//如果有其它棋⼦
flag=0;
}
}
if(flag)
{//如果两个棋⼦在同⼀列并且之间没有其它的棋⼦，返回20。
return20;
}
else
{//如果两个棋⼦在同⼀列并且之间有其它的棋⼦，返回21。
return21;
}
}
else
{//如果既不在同⼀⾏，也不在同⼀列，返回0.
return0;
}
}
void p_t_c_p_a_j_t_s_o_d(char type,int x,int y)
{//将输⼊的棋⼦放到棋盘上，并标记出该棋⼦统治的范围
switch(type)
{
case'G':
{//如果红棋是帅
for(int i=x+1;i>=1;i--)
for(int i=x+1;i>=1;i--)
{
if(CheckerboardR[i][y]==1||CheckerboardR[i][y]==2)
break;
else if(CheckerboardR[i][y]==0||CheckerboardR[i][y]==10)
CheckerboardR[i][y]=10;
}
}
case'R':
{//如果红棋是车
for(int i=x-1;i>=1;i--)
{
if(CheckerboardR[i][y]==1||CheckerboardR[i][y]==2)
break;
else if(CheckerboardR[i][y]==0||CheckerboardR[i][y]==10)
CheckerboardR[i][y]=10;
}
for(int i=x+1;i<=10;i++)
{
if(CheckerboardR[i][y]==1||CheckerboardR[i][y]==2)中国象棋入门
break;
else if(CheckerboardR[i][y]==0||CheckerboardR[i][y]==10)
CheckerboardR[i][y]=10;
}
for(int i=y+1;i<=9;i++)
{
if(CheckerboardR[i][y]==1||CheckerboardR[i][y]==2)
break;
else if(CheckerboardR[i][y]==0||CheckerboardR[i][y]==10)
CheckerboardR[x][i]=10;
}
for(int i=y-1;i>=1;i--)
{
if(CheckerboardR[i][y]==1||CheckerboardR[i][y]==2)
break;
else if(CheckerboardR[i][y]==0||CheckerboardR[i][y]==10)
CheckerboardR[x][i]=10;
}
}
case'H':
{//如果红棋是马
if(x+1==0||x+1==10)
{
CheckerboardR[x+2][y-1]=10;
CheckerboardR[x+2][y+1]=10;
}
if(x-1==0||x-1==10)
{
CheckerboardR[x-2][y-1]=10;
CheckerboardR[x+2][y+1]=10;
}
if(y-1==0||y-1==10)
{
CheckerboardR[x+1][y-2]=10;
CheckerboardR[x-1][y-2]=10;
}
if(y+1==0||y+1==10)
{
CheckerboardR[x+1][y+2]=10;
CheckerboardR[x-1][y+2]=10;
}
}
case'C':
{//如果红棋是炮
if(s_l_o_c_a_i_c(x,y,Generalx,Generaly)==11||s_l_o_c_a_i_c(x,y,Generalx,Generaly)==21) {//判断炮与⿊棋将军是否在同⼀条线上，以及中间是否有其它棋⼦
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论