HDU4121 UVa1589 Xiangqi 解题报告

http://acm.hdu.edu.cn/showproblem.php?pid=4121​
这是一道模拟的题，大致是中国象棋的规则，然后给你输入红方和黑方的棋子，然后再给出红方的其它棋子，其它棋子只能为 车、马、炮，且棋盘一共只有8个棋子。题目中的情况是，现在轮到黑方来移动棋子，来判断是否已经把黑方的将“将死”。首先读完题目，就知道这是一道模拟题。需要模拟象棋的规则，对棋盘进行操作。而且，我们看到的是所有黑将能移动的位置都应该被将死。值得注意的是，在将军的情况下，由于黑方只有一个将，所以将在输入时的最初位置的时候其实不必被将军，因为它必须移动，所以就算将了军也是无用的。
所以，我们可以把所有类型的象棋来进行模拟，看是否能吃到将。

规则见原题。

我在做题的时候犯了一个错误，将不能在九宫格中按斜线来走，那是士走的路线。而且我的方法不用考虑将可以吃掉棋子的情况。还有就是注意程序中bool类型变量的位置很重要。
下面上代码，我的代码很长，可以简化。

/*
    HDU4121 UVa1589 Xiangqi
    0MS 1408K(HDU)
    @author: mukeran
    @link: http://www.mukeran.com
*/
#include<cstdio>
#include<cstring>
/*
P 是一个结构体来记录点的数据
变量声明：mat 是 bool，用来记录当前棋盘上位置是否有棋子
          B 是 P，用来记录黑将的位置
          G 是 P，用来记录红将的位置
          R 是 P 的一个数组，用来记录所有车的位置
          cntr 是 int，用来记录有多少个车
          H 是 P 的一个数组，用来记录所有马的位置
          cnth 是 int，用来记录有多少个马
          C 是 P 的一个数组，用来记录所有炮的位置
          cntc 是 int，用来记录有多少个炮
          symbol 是 char，用来输入时记录
          x 和 y 是 int，输入时的记录和黑将位置的代表
          blacks 是一个 P 的二维数组，用来记录在每个位置上的黑将能走到哪个位置上
*/
struct P {
    int x;
    int y;
}B, G, R[10], H[10], C[10];
char symbol;
bool mat[15][12];
P blacks[12][12] = { //black[0]作废，black[i][0].x用来记录有多少种情况，black[i][j]是P，用来记录点位置
    {}, {{x:2}, {x:1, y:5}, {x:2, y:4}},
    {{x:3}, {x:1, y:4}, {x:3, y:4}, {x:2, y:5}},
    {{x:2}, {x:2, y:4}, {x:3, y:5}},
    {{x:3}, {x:1, y:4}, {x:1, y:6}, {x:2, y:5}},
    {{x:4}, {x:2, y:4}, {x:1, y:5}, {x:3, y:5}, {x:2, y:6}},
    {{x:3}, {x:3, y:4}, {x:3, y:6}, {x:2, y:5}},
    {{x:2}, {x:2, y:6}, {x:1, y:5}},
    {{x:3}, {x:1, y:6}, {x:3, y:6}, {x:2, y:5}},
    {{x:2}, {x:2, y:6}, {x:3, y:5}}
    //这里有一个记录规则，y = 5 时，x += 3，y = 6 时，x += 6，当然 y = 4 时 x 不变
    //这里可以用另外的循环来实现
};
int n, x, y, cntr, cnth, cntc;
int main() {
    while(true) {
        scanf("%d%d%d", &n, &B.x, &B.y);
        if(n == 0) return 0;
        //数据清零
        memset(mat, 0, sizeof mat);
        memset(R, 0, sizeof R);
        memset(H, 0, sizeof H);
        memset(C, 0, sizeof C);
        cntr = cnth = cntc = 0;
        //输入
        for(int i = 1; i <= n; i++) {
            scanf("%s%d%d", &symbol, &x, &y);
            mat[x][y] = true;
            if(symbol == 'G') G.x = x, G.y = y;
            else if(symbol == 'R') R[++cntr].x = x, R[cntr].y = y;
            else if(symbol == 'H') H[++cnth].x = x, H[cnth].y = y;
            else if(symbol == 'C') C[++cntc].x = x, C[cntc].y = y;
        }
        bool ans = false; //ans用来记录当前位置是否能将军
        //读取点会走的位置
        int index = B.x;
        if(B.y == 5) index += 3;
        else if(B.y == 6) index += 6;
        x = y = 0;
        bool rec = false; //rec用来记录当前黑王的位置是否会覆盖一个原来的棋子，在恢复棋盘的是否要恢复
        for(int w = 1; w <= blacks[index][0].x; w++) {
            if(!rec) mat[x][y] = false; //抹掉上个王的位置
            x = blacks[index][w].x, y = blacks[index][w].y; //读取下一个王的位置
            if(mat[x][y]) rec = true; //检查王此时的位置上原来是否有棋子，并记录
            else rec = false;
            mat[x][y] = true; //标记王的位置
            ans = false;
            //首先是判断红将能否直接飞过去吃到黑将
            if(G.y == y) {
                ans = true;
                for(int j = x + 1; j < G.x; j++)
                    if(mat[j][y]) {
                        ans = false;
                        break;
                    }
            }
            if(ans) continue; //如果已经将了，下面的就不用判断了
            //判断车是否能把王吃掉
            for(int j = 1; j <= cntr; j++) {
                if(R[j].x == x) { //横向
                    if(R[j].y < y) { //车在王左侧
                        ans = true;
                        for(int q = R[j].y + 1; q < y; q++)
                            if(mat[x][q]) {
                                ans = false;
                                break;
                            }
                    }
                    if(R[j].y > y) { //车在王右侧
                        ans = true;
                        for(int q = y + 1; q < R[j].y; q++)
                            if(mat[x][q]) {
                                ans = false;
                                break;
                            }
                    }
                }
                else if(R[j].y == y) { //纵向
                    if(R[j].x > x) { //车在王下侧
                        ans = true;
                        for(int q = x + 1; q < R[j].x; q++)
                            if(mat[q][y]) {
                                ans = false;
                                break;
                            }
                    }
                    if(R[j].x < x) { //车在王上侧
                        ans = true;
                        for(int q = R[j].x + 1; q < x; q++)
                            if(mat[q][y]) {
                                ans = false;
                                break;
                            }
                    }
                }
                if(ans) break;
            }
            if(ans) continue;
            //判断马
            for(int j = 1; j <= cnth; j++)
                if((H[j].x - 2 == x && (H[j].y - 1 == y || H[j].y + 1 == y) && !mat[H[j].x - 1][H[j].y])
                    ||(H[j].x + 2 == x && (H[j].y - 1 == y || H[j].y + 1 == y) && !mat[H[j].x + 1][H[j].y])
                    ||(H[j].y - 2 == y && (H[j].x - 1 == x || H[j].x + 1 == x) && !mat[H[j].x][H[j].y - 1])
                    ||(H[j].y + 2 == y && (H[j].x - 1 == x || H[j].x + 1 == x) && !mat[H[j].x][H[j].y + 1])) {
                    ans = true;
                    break;
                }
            if(ans) continue;
            //判断炮
            for(int j = 1; j <= cntc; j++) {
                if(C[j].x == x) { //横向
                    bool tmpf = false; //tmpf用来看炮和王之间是否会有多余的棋子
                    if(C[j].y < y) { //炮在王左边
                        ans = false;
                        for(int q = C[j].y + 1; q < y; q++)
                            if(mat[x][q]) {
                                if(tmpf) {
                                    ans = false; //第二次找到炮之间的棋子，废止
                                    break;
                                }
                                else {
                                    tmpf = true; //第一次找到炮之间的棋子，成立
                                    ans = true;
                                }
                            }
                    }
                    else if(C[j].y > y) { //炮在王右边
                        ans = false;
                        for(int q = C[j].y - 1; q > y; q--)
                            if(mat[x][q]) {
                                if(tmpf) {
                                    ans = false;
                                    break;
                                }
                                else {
                                    tmpf = true;
                                    ans = true;
                                }
                            }
                    }
                }
                else if(C[j].y == y) { //纵向
                    bool tmpf = false;
                    if(C[j].x > x) { //炮在王下面
                        ans = false;
                        for(int q = C[j].x - 1; q > x; q--)
                            if(mat[q][y]) {
                                if(tmpf) {
                                    ans = false;
                                    break;
                                }
                                else {
                                    tmpf = true;
                                    ans = true;
                                }
                            }
                    }
                    else if(C[j].x < x) { //上面
                        ans = false;
                        for(int q = C[j].x + 1; q < x; q++)
                            if(mat[q][y]) {
                                if(tmpf) {
                                    ans = false;
                                    break;
                                }
                                else {
                                    tmpf = true;
                                    ans = true;
                                }
                            }
                    }
                }
                if(ans) break;
            }
            //如果到这里都没有将军的话，则说明不能将军
            if(!ans) {
                printf("NO\n");
                break;
            }
        }
        //如果所有情况都能将军的话，就可以完全将军
        if(ans) printf("YES\n");
    }
}