ACM/ICPC 2011 福州现场赛 Xiangqi 题解
这道象棋模拟题其实还是比较简单的，但是写起来要注意的地方非常多。测试数据据说不太刁钻，比如那种黑方能够直接获胜的棋局（表现为一开始将帅之间就没有任何棋子而相对）是没有的。不过为了内心的宁静，我在代码里还是加上了这些特判内容。
赛后练习时提交了三次才 AC, 原因是判断红方马的时候不小心判断到了黑方 boss 的原来位置上（而正确的判断方法应该是黑方 boss 走一步之后的那个位置），后来检查了几遍才看出来。
这里面还有一些小技巧，就是可以专门写一个函数，判断两个棋子之间有多少个其它棋子，这样炮、车、帅就好复用了。其实这里面车的 behavior 和帅的基本上是一样的。
现场赛的时候是队长 Wideas 敲的，赛后他对我的教诲是，对于这种模拟题，数据范围并不是特别大，考点在于编程细心方面的，写起来就不要考虑太多执行效率上的问题了。嗯，所以这种题，应该怎么写爽，就怎么写。
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 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 | #include <cstdio> #include <cstring> using namespace std; int board[20][20]; int bossx, bossy, red_boss; int redcnt, redx[10], redy[10]; char redtype[10]; const int dirx[4] = { -1, 0, 1, 0}; const int diry[4] = { 0, 1, 0, -1}; const int horx[8] = { -2, -2, -1, 1, 2, 2, 1, -1}; const int hory[8] = { -1, 1, 2, 2, 1, -1, -2, -2}; const int NONE = 0; const int RED = 1; const int BLACK = 2; inline bool init_and_input() { memset(board, 0, sizeof board); scanf("%d %d %d", &redcnt, &bossx, &bossy); if (redcnt == 0 && bossx == 0 && bossy == 0) return false; char buf[8]; for (int i = 0; i < redcnt; ++i) { scanf("%s %d %d", buf, &redx[i], &redy[i]); redtype[i] = *buf; red_boss = -1; board[redx[i]][redy[i]] = RED; if (*buf == 'G') red_boss = i; } return true; } inline bool is_on_board(int x, int y) { if (x >= 1 && x <= 10 && y >= 1 && y <= 9) return true; return false; } inline bool is_in_palace(int x, int y) { if (x >= 1 && x <= 3 && y >= 4 && y <= 6) return true; if (x >= 8 && x <= 10 && y >= 4 && y <= 6) return true; return false; } inline int count_between(int index, int x, int y) { int delta = 0, result = 0; if (redx[index] == x) { if (y > redy[index]) delta = 1; else delta = -1; for (int i = redy[index] + delta; i != y; i += delta) if (board[x][i] != NONE) ++result; return result; } else if (redy[index] == y) { if (x > redx[index]) delta = 1; else delta = -1; for (int i = redx[index] + delta; i != x; i += delta) if (board[i][y] != NONE) ++result; return result; } return -1; } inline bool chariot_can_eat(int index, int x, int y) { return count_between(index, x, y) == 0; } inline bool general_can_eat(int index, int x, int y) { return chariot_can_eat(index, x, y); } inline bool cannon_can_eat(int index, int x, int y) { return count_between(index, x, y) == 1; } inline bool horse_can_eat(int index, int x, int y) { for (int i = 0; i < 8; ++i) { int destx = redx[index] + horx[i]; int desty = redy[index] + hory[i]; int footx = redx[index] + dirx[i >> 1]; int footy = redy[index] + diry[i >> 1]; if (!is_on_board(destx, desty)) continue; if (!is_on_board(footx, footy)) continue; if (board[footx][footy] != NONE) continue; if (destx == x && desty == y) return true; } return false; } inline bool can_eat(int index, int x, int y) { switch (redtype[index]) { case 'G': return general_can_eat(index, x, y); case 'R': return chariot_can_eat(index, x, y); case 'C': return cannon_can_eat(index, x, y); case 'H': return horse_can_eat(index, x, y); } return false; } int main() { // freopen("input.txt", "r", stdin); while (init_and_input()) { if (count_between(red_boss, bossx, bossy) == 0) { printf("NO\n"); break; } bool result = true; for (int i = 0; i < 4; ++i) { int x = bossx + dirx[i]; int y = bossy + diry[i]; if (!is_in_palace(x, y)) continue; int before = board[x][y]; board[x][y] = BLACK; bool eat = false; for (int j = 0; j < redcnt; ++j) { if (board[redx[j]][redy[j]] != RED) continue; if (can_eat(j, x, y)) { eat = true; break; } } if (!eat) { result = false; break; } board[x][y] = before; } if (result) printf("YES\n"); else printf("NO\n"); } return 0; } |
