首页 > ACM题库 > HDU-杭电 > HDU 1691 Chinese Chess[解题报告] C++
2013
12-21

HDU 1691 Chinese Chess[解题报告] C++

Chinese Chess

问题描述 :

Chinese chess, or Xiangqi is an extremely popular game in the Eastern Hemisphere. It is currently played by millions (or tens of millions) in China’s mainland, Taiwan, Thailand, Singapore, Vietnam, Hong Kong and other Asian countries. Chinese chess has remained in its present form for centuries.
The name Chinese chess has an interesting origin. Of China’s four traditional arts — qin (music), qi (strategy games), shu (calligraphy) and hua (brush painting) — the second term, qi, provides the final syllable of Chinese chess.

Here’s some more information about Chinese chess.

Chinese chess Board

Pieces
Each player has the following pieces:
2 Rooks (R) (or chariots)
2 Knights (N) (or horses)
2 Elephants (M) (or bishops or ministers)
2 Mandarins (G) (or advisors or assistants or guards)
1 King (K) (or generals)
2 Cannons (C)
5 Pawns (P) (or soldiers)

Rules
a) The object of the game is to checkmate or stalemate the opponent. This is accomplished by:
Placing the opponent in check so that he has no legal move to get out of the check.
Stalemating your opponent so that he has no legal move (when you stalemate your opponent, you win–it is not a draw as in chess).
b) Red usually moves first.
c) You cannot check your opponent indefinitely by moving the same piece to the same squares (resulting in perpetual check and a draw in chess). You cannot put the opponent in check more than 3 times in a row with the same piece without either side moving any other piece.
d) Similar to the rule above, you cannot indefinitely "chase" an opposing piece from one square to another if your opponent has no other way to avoid losing the piece. The idea of this rule and the rule above is to avoid perpetual check draws. Some of these situations can be complicated but usually the person who is initiating the perpetual move loop must break it off.
e) The two kings cannot face each other on the same column without any pieces between them.
f) When neither side can capture the opposing king, the game is a draw.

Now your group is developing a Chinese chess software. It’s your task to write a program to check if the moves are legal or not. To simplify this problem, you needn’t to consider the rule b, c, d, f. It means that the result is not important. The only thing you need to do is to judge if the moves are legal. A move is illegal if:
a)  The given coordinates of original and final position are illegal. Such as the position is out of the board, the original position is empty or your opponent’s piece or the final position is your own piece.
b)  The move breaks the move rules and rules above (except rule b, c, d, f)
c)  Something special, if after one move, one of the player’s king has been eaten, if it’s the last move, it’s legal, or the next move is illegal. (look at the sample for more details)

输入:

  The input consists of several test cases. There is a single number above all, the number of cases. There are no more than 300 cases.
  Each case starts with the initial chess board. There are 10 rows and 9 columns. 0 represents empty point. 1, 2, 3, 4, 5, 6, 7 represent red king, mandarin, elephant, knight, rook, cannon, pawn while 8, 9, 10, 11, 12, 13, 14 represent black pieces. Then two numbers N and K ( ): n is the number of moves and if K=0 red moves first, if K=1 black moves first. Next N lines follow, each containing four integers, representing the coordinates of original position and final position. You may assume that the initial board is always legal. For more details, the board of figure 1 is:
12 11 10 9 8 9 10 11 12
0 0 0 0 0 0 0 0 0
0 13 0 0 0 0 0 13 0
14 0 14 0 14 0 14 0 14
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
7 0 7 0 7 0 7 0 7
0 6 0 0 0 0 0 6 0
0 0 0 0 0 0 0 0 0
5 4 3 2 1 2 3 4 5

输出:

If all of the moves are legal, print “Legal move”. If step x is the first illegal move, then print “Illegal move on step x”. If there are several moves are illegal, print the first illegal move only. Use the format in the sample.

样例输入:

3
0 0 0 9 8 0 0 0 0
0 0 0 0 9 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 11 0
0 0 0 0 0 0 0 0 0
0 0 0 0 2 0 0 0 5
0 0 0 2 1 0 0 0 0
3 1
7 8 8 6
9 9 9 6
8 6 10 5
0 0 0 0 8 0 0 0 0
0 0 0 0 7 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 14 1 0 0 0 0
1 0
2 5 1 5
0 0 0 0 8 0 0 0 0
0 0 0 0 7 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 14 1 0 0 0 0
2 0
2 5 1 5
10 4 10 5

样例输出:

Case 1: Illegal move on step 3
Case 2: Legal move
Case 3: Illegal move on step 2

http://acm.hdu.edu.cn/showproblem.php?pid=1691

博客里面不好骂人,所以就不说太多了。

有几点注意:

1、象可能跑到不可能达到的位置

2、兵要判断后退这种情况

#include <stdio.h>
 
 int map[20][20];
 int Kinga,Kingb;//红王坐标 
 int Kingc,Kingd;//黑王坐标 
 int abs(int a){return a>0?a:-a;}
 int KingFaceToFace()//两王是否相对 
 {
     int i;
     if(Kingb==20||Kingd==20)return 0;
     if(Kingb==Kingd)
     {
         for(i=Kingc+1;i<Kinga;i++)
             if(map[i][Kingb]!=0)
                 return 0;
         return 1;
     }
     return 0;
 }
 int King(int a,int b,int c,int d)
 {
     if((abs(a-c)+abs(b-d))!=1)return 0;//王一次走一步 
     if(map[a][b]==1&&(a<8||b<4||b>6||c<8||d<4||d>6))//红王出九宫格 
         return 0;
     if(map[a][b]==8&&(a>3||b<4||b>6||c>3||d<4||d>6))//黑王出九宫格
         return 0;
     if(map[a][b]==1){
         Kinga=c;
         Kingb=d;
     }
     if(map[a][b]==8){
         Kingc=c;
         Kingd=d;
     }
     map[c][d]=map[a][b];
     map[a][b]=0; 
     if(KingFaceToFace())
         return 0;
     return 1;
 }
 int Mandarins(int a,int b,int c,int d)
 {
     if(abs(a-c)!=1||abs(b-d)!=1)return 0;//士走斜一格
     if(map[a][b]==2&&(c<8||c>10||d<4||d>6))//红士出九宫格 
         return 0;
     if(map[a][b]==9&&(c>3||c<1||d<4||d>6))//黑士出九宫格
         return 0;
     map[c][d]=map[a][b];
     map[a][b]=0; 
     if(KingFaceToFace())
         return 0;
     return 1;
 }
 int Elephants(int a,int b,int c,int d)
 {
     if(abs(a-c)!=2||abs(b-d)!=2)return 0;//象走田 
     if(map[a][b]==3&&(!(((a==6||a==10)&&(b==3||b==7))||(a==8&&(b==1||b==5||b==9)))||!(((c==6||c==10)&&(d==3||d==7))||(c==8&&(d==1||d==5||d==9)))))return 0;//红象非主流 
     if(map[a][b]==10&&(!(((a==5||a==1)&&(b==3||b==7))||(a==3&&(b==1||b==5||b==9)))||!(((c==5||c==1)&&(d==3||d==7))||(c==3&&(d==1||d==5||d==9)))))return 0;//黑象非主流 
     int x,y;
     x=(a+c)/2;
     y=(b+d)/2;
     if(map[x][y])//别象脚 
         return 0;
     map[c][d]=map[a][b];
     map[a][b]=0;
     if(KingFaceToFace())
         return 0;
     return 1; 
 } 
 int Knights(int a,int b,int c,int d)
 {
     int luoma[8][2]={{2,1},{2,-1},{-2,1},{-2,-1},{1,2},{1,-2},{-1,2},{-1,-2}};//落马的位置 
     int majiao[8][2]={{1,0},{1,0},{-1,0},{-1,0},{0,1},{0,-1},{0,1},{0,-1}};//马脚的位置 
     int i;
     for(i=0;i<8;i++)
     {
         if(a+luoma[i][0]==c&&b+luoma[i][1]==d)
         {
             if(map[a+majiao[i][0]][b+majiao[i][1]])//别马脚 
                 return 0;
             break;
         }
     }
     if(i==8)return 0;
     if(map[c][d]==1)Kinga=Kingb=20;
     if(map[c][d]==8)Kingc=Kingd=20;
     map[c][d]=map[a][b];
     map[a][b]=0;
     if(KingFaceToFace())
         return 0;
     return 1;
 }
 int Rooks(int a,int b,int c,int d)
 {
     int i;
     if(a!=c&&b!=d)return 0;//车走十字 
     if(a==c&&d>b)//车向右走中间不能有子 
         for(i=b+1;i<d;i++)
             if(map[a][i])
                 return 0;
     if(a==c&&d<b)//车向左走中间不能有子
         for(i=b-1;i>d;i--)
             if(map[a][i])
                 return 0;
     if(b==d&&a>c)//车向上走中间不能有子 
         for(i=a-1;i>c;i--)
             if(map[i][b])
                 return 0;
     if(b==d&&a<c)//车向下走中间不能有子 
         for(i=a+1;i<c;i++)
             if(map[i][b])
                 return 0;
     if(map[c][d]==1)Kinga=Kingb=20;
     if(map[c][d]==8)Kingc=Kingd=20;
     map[c][d]=map[a][b];
     map[a][b]=0;
     if(KingFaceToFace())
         return 0;
     return 1; 
 }
 int Cannons(int a,int b,int c,int d)
 {
     int i,cnt=0;
     if(a!=c&&b!=d)return 0;//炮走十字 
     if(a==c&&d>b) 
     {
         for(i=b+1;i<d;i++)
             if(map[a][i]!=0)
                 cnt++;
         if(cnt>1||(cnt==1&&map[c][d]==0)||(cnt==0&&map[c][d]))return 0;//中间有一子以上或有一子但不能完成吃子 
     }
     if(a==c&&d<b)
     {
         for(i=b-1;i>d;i--)
             if(map[a][i]!=0)
                 cnt++;
         if(cnt>1||(cnt==1&&map[c][d]==0)||(cnt==0&&map[c][d]))return 0;
     }
     if(b==d&&a>c) 
     {
         for(i=a-1;i>c;i--)
             if(map[i][b]!=0)
                 cnt++;
         if(cnt>1||(cnt==1&&map[c][d]==0)||(cnt==0&&map[c][d]))return 0;
     }
     if(b==d&&a<c)
     {
         for(i=a+1;i<c;i++)
             if(map[i][b]!=0)
                 cnt++; 
         if(cnt>1||(cnt==1&&map[c][d]==0)||(cnt==0&&map[c][d]))return 0;
     }
     if(map[c][d]==1)Kinga=Kingb=20;
     if(map[c][d]==8)Kingc=Kingd=20;
     map[c][d]=map[a][b];
     map[a][b]=0;
     if(KingFaceToFace())
         return 0;
     return 1;
 }
 int Pawns(int a,int b,int c,int d)
 {
     if(abs(a-c)+abs(b-d)!=1)return 0;
     if(map[a][b]==14&&a<=5)//黑兵没过河只能向前走一步 
         if(c-a!=1||b!=d)
             return 0;
     if(map[a][b]==7&&a>=6)//红兵没过河只能向前走一步
         if(c-a!=-1||b!=d)
             return 0;
     if(map[a][b]==14&&a>5)//黑兵过河后能向前或左或右走一步 
         if(c-a==-1)
             return 0; 
     if(map[a][b]==7&&a<6)//红兵过河后能向前或左或右走一步
         if(c-a==1)
             return 0;
     if(map[c][d]==1)Kinga=Kingb=20;
     if(map[c][d]==8)Kingc=Kingd=20;
     map[c][d]=map[a][b];
     map[a][b]=0;
     if(KingFaceToFace())
         return 0;
     return 1; 
 }
 int move(int a,int b,int c,int d,int k)
 {
     if(map[a][b]<=k*7||map[a][b]>k*7+7)//红黑方不按顺序走 
         return 0;
     if(a>10||b>9||c>10||d>9||a<1||b<1||c<1||d<1)return 0;//越界 
     if(map[a][b]==0)return 0;//无子
     if((map[a][b]==1||map[a][b]==2||map[a][b]==3||map[a][b]==4||map[a][b]==5||map[a][b]==6||map[a][b]==7)&&(map[c][d]==1||map[c][d]==2||map[c][d]==3||map[c][d]==4||map[c][d]==5||map[c][d]==6||map[c][d]==7)) 
         return 0;//红方吃自己的子
     if((map[a][b]==8||map[a][b]==9||map[a][b]==10||map[a][b]==11||map[a][b]==12||map[a][b]==13||map[a][b]==14)&&(map[c][d]==8||map[c][d]==9||map[c][d]==10||map[c][d]==11||map[c][d]==12||map[c][d]==13||map[c][d]==14))
         return 0;//黑方吃自己的子 
     if(map[a][b]==1||map[a][b]==8)//走王 
         return King(a,b,c,d);
     if(map[a][b]==2||map[a][b]==9)//走士 
         return Mandarins(a,b,c,d);
     if(map[a][b]==3||map[a][b]==10)//走象 
         return Elephants(a,b,c,d);
     if(map[a][b]==4||map[a][b]==11)//走马 
         return Knights(a,b,c,d);
     if(map[a][b]==5||map[a][b]==12)//走车 
         return Rooks(a,b,c,d);
     if(map[a][b]==6||map[a][b]==13)//走炮 
         return Cannons(a,b,c,d);
     if(map[a][b]==7||map[a][b]==14)//走兵 
         return Pawns(a,b,c,d);
 } 
 int main()
 {
     int t;
     int n,k;
     int a,b,c,d;
     int i,j;
     int nCase=1;
     int step;
     scanf("%d",&t);
     while(t--)
     {
         for(i=1;i<=10;i++)
         {
             for(j=1;j<=9;j++)
             {
                 scanf("%d",&map[i][j]);
                 if(map[i][j]==1){
                     Kinga=i;
                     Kingb=j;
                 }
                 if(map[i][j]==8){
                     Kingc=i;
                     Kingd=j;
                 }
             }
         }
         scanf("%d%d",&n,&k);
         step=0;
         for(i=1;i<=n;i++)
         {
             scanf("%d%d%d%d",&a,&b,&c,&d);
             if(!step)
             {
                 if(!move(a,b,c,d,k))//非法移动 
                     step=i;
                 if(i!=n&&(Kingb==20||Kingd==20))//吃王 
                     step=i+1;
             }
             k=!k;
         }
         printf("Case %d: ",nCase++);
         if(!step)
             printf("Legal move\n");
         else
             printf("Illegal move on step %d\n",step);
     }
     return 0;
 }

 

 

解题报告转自:http://www.cnblogs.com/xiaohongmao/archive/2012/04/19/2456841.html


  1. 漂亮。佩服。
    P.S. unsigned 应该去掉。换行符是n 不是/n
    还可以稍微优化一下,
    int main() {
    int m,n,ai,aj,bi,bj,ak,bk;
    while (scanf("%d%d",&m,&n)!=EOF) {
    ai = sqrt(m-1);
    bi = sqrt(n-1);
    aj = (m-ai*ai-1)>>1;
    bj = (n-bi*bi-1)>>1;
    ak = ((ai+1)*(ai+1)-m)>>1;
    bk = ((bi+1)*(bi+1)-n)>>1;
    printf("%dn",abs(ai-bi)+abs(aj-bj)+abs(ak-bk));
    }
    }

  2. Thanks for using the time to examine this, I truly feel strongly about it and enjoy finding out far more on this subject matter. If achievable, as you achieve knowledge

  3. L(X [0 .. M-1],Y [0 .. N-1])= 1 + L(X [0 .. M-2],Y [0 .. N-1])这个地方也也有笔误
    应改为L(X [0 .. M-1],Y [0 .. N-1])= 1 + L(X [0 .. M-2],Y [0 .. N-2])