原題及翻譯

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; 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。return 10;}else{//如果兩個棋子在同一行并且之間有其它的棋子，返回11。return 11;}}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。return 20;}else{//如果兩個棋子在同一列并且之間有其它的棋子，返回21。return 21;}}else{//如果既不在同一行，也不在同一列，返回0.return 0;} } 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--){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){//判斷炮與黑棋將軍是否在同一條線上，以及中間是否有其它棋子for(int i=x-1;i>=1;i--){int x1=0,y1=0;if(CheckerboardR[i][y]==1&&CheckerboardR[i][y]==2){x1=i;y1=y;{for(int j=x1-1;i>=1;j--){if(CheckerboardR[j][y]==1&&CheckerboardR[j][y]==2)break;elseCheckerboardR[j][y]=10;}}}}}for(int i=y-1;i>=1;i--){int x1=0,y1=0;if(CheckerboardR[x][i]==1&&CheckerboardR[x][i]==2){x1=x;y1=i;for(int j=y1-1;i>=1;j--){if(CheckerboardR[x][j]==1&&CheckerboardR[x][j]==2)break;elseCheckerboardR[x][j]=10;}}}for(int i=y+1;i<=9;i++){int x1=0,y1=0;if(CheckerboardR[x][i]==1&&CheckerboardR[x][i]==2){x1=x;y1=i;for(int j=y1+1;i<=9;j++){if(CheckerboardR[x][j]==1&&CheckerboardR[x][j]==2)break;elseCheckerboardR[x][j]=10;}}}}} } int main () {//主函數，用于輸入數據和做最后的判斷memset(CheckerboardR,0,sizeof(CheckerboardR));memset(CheckerboardB,0,sizeof(CheckerboardB));while(1){cin>>red_number>>Generalx>>Generaly;//讀入紅方棋子是數和黑棋將軍的坐標，這些坐標都作為全局變量聲明CheckerboardB[Generalx][Generaly]=2;//在黑棋盤上將黑棋將軍的坐標記錄下來if(red_number==0||Generalx==0||Generaly==0) break;//用于結束輸入struct piece red_piece[red_number];//聲明一個存儲紅棋棋子結構的數組for(int i=1;i<=red_number;i++){//將red_number行的紅棋子數據讀入cin>>red_piece[i].type;scanf("%d %d",&red_piece[i].x,&red_piece[i].y);//存儲紅棋棋子的類型和坐標CheckerboardR[red_piece[i].x][red_piece[i].y]=1;//在紅棋棋盤上把相應的位置標出來}for(int i=1;i<=red_number;i++){//利用函數將red_number行紅棋的攻擊范圍標識出來p_t_c_p_a_j_t_s_o_d(red_piece[i].type,red_piece[i].x,red_piece[i].y);}General_scope(Generalx,Generaly);//調用函數將黑棋將軍的移動范圍標識出來//開始判斷黑棋移動范圍是否是紅棋攻擊范圍的子集int checkmate1=0,checkmate2=0; //定義判斷是否“將死”的變量for(int i=1;i<=3;i++){for(int j=4;j<=6;j++){/*經過一系列的函數處理之后，紅棋的攻擊范圍與黑棋的移動范圍被標識出來*/if(CheckerboardB[i][j]==20) checkmate1++;//如果遇到黑棋盤上標有20的位置，累加checkmate1if(CheckerboardB[i][j]==20&&CheckerboardR[i][j]==10) checkmate2++;//如果遇到黑棋盤上標有20，紅棋盤上標有10的位置，累加checkmate2}}if(checkmate1==checkmate2) printf("YES \n");else printf("NO \n");memset(CheckerboardR,0,sizeof(CheckerboardR));memset(CheckerboardB,0,sizeof(CheckerboardB));//將兩張棋盤重置，為下次輸入做準備} return 0; }

測試

結語

看來英語不好也是個大問題啊，不然連ACM的題目都看不懂。
還有，百度翻譯，哎，無力吐槽。

每天磕一道ACM 2月1日打卡

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的《算法竞赛入门经典》 习题4-1（象棋 Xiangqi ACM ICPC Fuzhou 2011，UVa1589）——仅提供大体方法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。