问题描述
p1589原题链接：UVaOJ 1589 - Xiangqi
相关说明：本题为《算法竞赛入门经典（第2版）》习题 4-1
解法一：模拟
大模拟，需要注意蛮多细节。我的实现中用 board 把当前棋盘落字有无的情况存下来， board[x][y]=0 表示对应位置没有红方棋子，同时将红方棋子按照类型进行记录。这里设置了一个辅助函数 interval 表示两个棋子之间有多少个间隔棋子，可以用来判断能否直接飞将帅、车能否吃以及炮能否打过去；而在判断马棋盘上的马能否吃到移动后的黑将时，用到了一个规律，即如果能吃到，两个棋子之间的斜线距离是根号 5, 且 board[mx][my] 处没有棋子阻挡。代码中用到了比较多的 dir定义的技巧来判断移动的方向，可以少写些 if-else.
判断黑方是否已经走投无路的整体思路是：
- 如果黑将当前移动能够直接飞过去把对面红帅吃了，输出 NO;
- 否则尝试所有可以移动的方向，看是否存在某种移动后不会被红方吃掉，有任意解则输出 NO;
- 上述条件都不存在的话，输出 YES.
|
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 |
#include <bits/stdc++.h> using namespace std; int board[11][10]; // Value 0 means no red piece here int black_gx, black_gy, white_gx, white_gy; vector<pair<int, int>> chariot, horse, cannon; int interval(int x1, int y1, int x2, int y2) { int num = 0; if (x1 != x2 && y1 != y2) return -1; // not in the same line if (x1 == x2 && y1 == y2) return -1; // in the same point if (x1 == x2) { int dir = (y2 - y1) > 0 ? 1 : -1; for (int p = y1 + dir; p != y2; p += dir) if (board[x1][p]) ++num; } else if (y1 == y2) { int dir = (x2 - x1) > 0 ? 1 : -1; for (int p = x1 + dir; p != x2; p += dir) if (board[p][y1]) ++num; } return num; } bool capture(int x, int y) { if (interval(x, y, white_gx, white_gy) == 0) return true; for (auto r : chariot) if (interval(x, y, r.first, r.second) == 0) return true; for (auto h : horse) if (abs(pow(x - h.first, 2) + pow(y - h.second, 2) - 5) < 1e-5) { int mx = h.first + (x - h.first) / 2; int my = h.second + (y - h.second) / 2; if (!board[mx][my]) return true; } for (auto c : cannon) if (interval(x, y, c.first, c.second) == 1) return true; return false; } int main() { int n, px, py; string type, blank_line; while (cin >> n >> black_gx >> black_gy) { if (!n && !black_gx && !black_gy) break; memset(board, 0, sizeof(board)); chariot.clear(), horse.clear(), cannon.clear(); while (n--) { cin >> type >> px >> py; board[px][py] = 1; if (type == "G") white_gx = px, white_gy = py; if (type == "R") chariot.push_back(pair<int, int>{px, py}); if (type == "H") horse.push_back(pair<int, int>{px, py}); if (type == "C") cannon.push_back(pair<int, int>{px, py}); } // Flying general if (interval(black_gx, black_gy, white_gx, white_gy) == 0) { cout << "NO" << endl; continue; } if (interval(black_gx, black_gy, white_gx, white_gy) == 0 || (black_gx > 1 && !capture(black_gx - 1, black_gy)) || (black_gx < 3 && !capture(black_gx + 1, black_gy)) || (black_gy > 4 && !capture(black_gx, black_gy - 1)) || (black_gy < 6 && !capture(black_gx, black_gy + 1))) cout << "NO" << endl; else cout << "YES" << endl; getline(cin, blank_line); } return 0; } |
|
1 |
#TODO |
