Uva- 1589 - Xiangqi

Posted on | Edited on

象棋（Xiangqi, ACM/ICPC Fuzhou 2011, UVa1589）

原题地址：Uva1589

考虑一个象棋残局，其中红方有n（2≤n≤7）个棋子，黑方只有一个将。红方除了有一个帅（G）之外还有3种可能的棋子：车（R），马（H），炮（C），并且需要考虑“蹩马腿”（如图4-4所示）与将和帅不能照面（将、帅如果同在一条直线上，中间又不隔着任何棋子的情况下，走子的一方获胜）的规则。

输入所有棋子的位置，保证局面合法并且红方已经将军。你的任务是判断红方是否已经把黑方将死。关于中国象棋的相关规则请参见原题。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
/**
 * 1589 - Xiangqi
 */
#include <iostream>
#include <array>

using namespace std;

struct Point {
    int x, y;
    char type;
};

int hasPartition(const array<Point, 7> &reds, const Point &p1, const Point &p2, int redNum){
    int partitionNum = 0;
    if(p1.x != p2.x && p1.y != p2.y)    //都不在同一条线上，肯定没有分隔子
        return 0;
    else if(p1.x == p2.x){
        int spanY = p1.y - p2.y;
        for(int i = 0; i < redNum; i++){
            if(reds[i].x == p1.x && ((spanY > 0 && reds[i].y > p2.y && reds[i].y < p1.y) || (spanY < 0 && reds[i].y > p1.y && reds[i].y < p2.y)))
                ++partitionNum;
        }
    } else {
        int spanX = p1.x - p2.x;
        for(int i = 0; i < redNum; i++){
            if(reds[i].y == p1.y && ((spanX > 0&& reds[i].x > p2.x && reds[i].x < p1.x) || (spanX < 0 && reds[i].x > p1.x && reds[i].x < p2.x)))
                ++partitionNum;
        }
    }
    return partitionNum;
}

bool judgeG(const array<Point, 7> &reds, const Point &blackG, int redNum, int pos) {
    if(reds[pos].y != blackG.y)
        return false;
    return hasPartition(reds, blackG, reds[pos], redNum) == 0;
}

bool judgeR(const array<Point, 7> &reds, const Point &blackG, int redNum, int pos) {
    if(reds[pos].x != blackG.x && reds[pos].y != blackG.y)
        return false;
    return hasPartition(reds, reds[pos], blackG, redNum) == 0;
}

bool judgeC(const array<Point, 7> &reds, const Point &blackG, int redNum, int pos) {
    if(reds[pos].x != blackG.x && reds[pos].y != blackG.y)
        return false;
    return hasPartition(reds, reds[pos], blackG, redNum) == 1;
}

bool judgeH(const array<Point, 7> &reds, const Point &blackG, int redNum, int pos) {
    int subX = blackG.x - reds[pos].x;
    int subY = blackG.y - reds[pos].y;
    if(subX == 0 || subY == 0)
        return false;
    if(abs(subX) + abs(subY) != 3)      //在不考虑绊马脚的情况下是否可达
        return false;

    if(abs(subX) == 2){
        for(int i = 0; i < redNum; i++){
            if(reds[i].x == reds[pos].x + (subX / 2) && reds[i].y == reds[pos].y)   //检查是否绊马脚
                return false;
        }
    } else {
        for(int i = 0; i < redNum; i++){
            if(reds[i].y == reds[pos].y + (subY / 2) && reds[i].x == reds[pos].x)   //检查是否绊马脚
                return false;
        }
    }
    return true;
}

bool judge(const array<Point, 7> &reds, const Point &blackG, int redNum) {
    for (int i = 0; i < redNum; i++) {
        if(reds[i].x == blackG.x && reds[i].y == blackG.y)      //被吃掉的子
            continue;
        switch (reds[i].type) {
            case 'G':       //将
                if (judgeG(reds, blackG, redNum, i))
                    return true;
                break;
            case 'C':       //炮
                if (judgeC(reds, blackG, redNum, i))
                    return true;
                break;
            case 'H':       //马
                if (judgeH(reds, blackG, redNum, i))
                    return true;
                break;
            case 'R':       //车
                if (judgeR(reds, blackG, redNum, i))
                    return true;
                break;
            default:
                break;
        }
    }
    return false;
}

bool isInBound(const array<Point, 7> &reds, Point &blackG, int redNum){
    return blackG.y >= 4 && blackG.y <= 6 && blackG.x >= 1 && blackG.x <= 3;
}

bool doJudge(const array<Point, 7> &reds, const Point &blackG, int redNum){
    Point a{};
    a = blackG;
    if(!judge(reds, a, redNum))
        return false;
    a.x += 1;
    if(isInBound(reds, a, redNum) && !judge(reds, a, redNum))
        return false;
    a.x -= 2;
    if(isInBound(reds, a, redNum) && !judge(reds, a, redNum))
        return false;
    a.x += 1;
    a.y += 1;
    if(isInBound(reds, a, redNum) && !judge(reds, a, redNum))
        return false;
    a.y -= 2;
    return !(isInBound(reds, a, redNum) && !judge(reds, a, redNum));

}
int main() {
    int redNum;
    Point blackG{};
    array<Point, 7> reds{};
    while (cin >> redNum >> blackG.x >> blackG.y) {
        if (redNum == 0)
            break;
        for (int i = 0; i < redNum; i++)
            cin >> reds[i].type >> reds[i].x >> reds[i].y;
        cout << (doJudge(reds, blackG, redNum) ? "YES" : "NO") << endl;
    }
}
坚持原创技术分享，您的支持将鼓励我继续创作！