Description:
Xiangqi is one of the most popular two-player board games in China. The game represents a battle between two armies with the goal of capturing the enemy’s “general” piece. In this problem, you are given a situation of later stage in the game. Besides, the red side has already “delivered a check”. Your work is to check whether the situation is “checkmate”.
Now we introduce some basic rules of Xiangqi. Xiangqi is played on a 10×9 board and the pieces are placed on the intersections (points). The top left point is (1,1) and the bottom right point is (10,9). There are two groups of pieces marked by black or red Chinese characters, belonging to the two players separately. During the game, each player in turn moves one piece from the point it occupies to another point. No two pieces can occupy the same point at the same time. A piece can be moved onto a point occupied by an enemy piece, in which case the enemy piece is "captured" and removed from the board. When the general is in danger of being captured by the enemy player on the enemy player’s next move, the enemy player is said to have "delivered a check". If the general's player can make no move to prevent the general's capture by next enemy move, the situation is called “checkmate”.
We only use 4 kinds of pieces introducing as follows:
General: the generals can move and capture one point either vertically or horizontally and cannot leave the “palace” unless the situation called “flying general” (see the figure above). “Flying general” means that one general can “fly” across the board to capture the enemy general if they stand on the same line without intervening pieces.
Chariot: the chariots can move and capture vertically and horizontally by any distance, but may not jump over intervening pieces
Cannon: the cannons move like the chariots, horizontally and vertically, but capture by jumping exactly one piece (whether it is friendly or enemy) over to its target.
Horse: the horses have 8 kinds of jumps to move and capture shown in the left figure. However, if there is any pieces lying on a point away from the horse horizontally or vertically it cannot move or capture in that direction (see the figure below), which is called “hobbling the horse’s leg”.
Now you are given a situation only containing a black general, a red general and several red chariots, cannons and horses, and the red side has delivered a check. Now it turns to black side’s move. Your job is to determine that whether this situation is “checkmate”.
Input
There is a blank line between two test cases. The input ends by 0 0 0.
Output
Sample Input
Sample Output
Hint
1 /* G是主将，R是车，H是马，C是炮，考虑蹩马腿，将帅不能照面 , 题目暗示下一步走棋的是黑方 2 * validMoveH 函数中的参数direct的值代表的马移动的方位，如下图 3 * 4 * (1)* (2)* 5 * 6 * (3)* (4)* 7 * 8 * (5)* (6)* 9 * 10 * (7)* (8)* 11 */ 12 13 #include <iostream> 14 #include <vector> 15 #include <cstring> 16 #include <algorithm> 17 using namespace std; 18 enum TRAVERSE_TYPE{ X,Y }; // 区间遍历枚举类型 19 enum MOVE_TYPE{ UP,DOWN,LEFT,RIGHT }; // 移动方向枚举类型 20 struct Pos{ 21 Pos(int nX,int nY):x(nX),y(nY) { } 22 Pos() = default; 23 int x; 24 int y; 25 }; 26 vector<Pos> R,H,C; // 储存棋盘上红⽅存在的⼦ 27 int map[100][100]; // 模拟棋盘 28 char mmap[100][100]; // 存储红方除主将外落⼦的类型 29 Pos general_b,general_r; // ⿊⽅、红⽅主将位置 30 int others(int begin,int end,int index,TRAVERSE_TYPE type); // 返回某个区间段上落⼦的个数 31 vector<MOVE_TYPE> validMoveG(); // 返回⼀个⿊将可以⾛的⽅向的stack 32 bool gensfight(Pos t); // 两主将照⾯的情况 33 bool RfightG(); // 红⽅⻋⾯对⿊⽅将情况 34 bool HfightG(); // 红⽅⻢⾯对⿊⽅将情况 35 bool CfightG(); // 红⽅炮⾯对⿊⽅将情况 36 bool RUN(int x,int y); // 将所有情况跑⼀遍 37 bool validMoveH(int x,int y,int direct); // 判断⻢⾛的情况是否合法 38 void erasing(int x,int y); // ⿊主将⾛过的地⽅如果有落⼦会被抹掉 39 40 int main() 41 { 42 int n; 43 while(cin >> n >> general_b.x >> general_b.y 44 && n && general_b.x && general_b.y){ // 主循环 45 R.clear(); H.clear(); C.clear(); 46 memset(map,0,sizeof(map));memset(mmap,0,sizeof(mmap)); 47 map[general_b.x][general_b.y] = 1; // 先将黑主将录入棋盘 48 while(n--) 49 { 50 char type; int posX; int posY; 51 cin >> type >> posX >> posY; 52 map[posX][posY] = 1; // 在每次询问中，不管输入什么类型落子，先录入棋盘 53 if(type == 'G'){ // 类型为红方主将 54 general_r.x = posX; 55 general_r.y = posY; 56 }else if(type == 'R'){ // 类型为红方车 57 R.emplace_back(Pos(posX,posY)); 58 mmap[posX][posY] = 'R'; // mmap数组的作用可在之后的erasing函数中清楚 59 }else if(type == 'H'){ // 类型为红方马 60 H.emplace_back(Pos(posX,posY)); 61 mmap[posX][posY] = 'H'; 62 }else{ // 类型为红方炮 63 C.emplace_back(Pos(posX,posY)); 64 mmap[posX][posY] = 'C'; 65 } 66 } 67 if(gensfight({general_b.x,general_b.y})){ // 分支1：直接出现主将对⾯情况 68 cout <<"NO" << endl; continue; 69 } 70 /* 分支2 (不出现主将直接面对)*/ 71 auto op = validMoveG(); // 获得⿊⽅主将可⾛⽅向的vector数组 72 bool yes; // yes若为true表示红方已将死黑方 73 for(auto &e : op){ // 只要⿊⽅主将有⼀种⾛法不会被将死就输出NO 74 yes = false; 75 // general_b 与 general_r 分别代表黑方主将与红方主将,见17行声明 76 if(e == MOVE_TYPE::UP && RUN(general_b.x-1,general_b.y)) yes = true; 77 else if(e == MOVE_TYPE::DOWN && RUN(general_b.x+1,general_b.y)) yes = true; 78 else if(e == MOVE_TYPE::LEFT && RUN(general_b.x,general_b.y-1)) yes = true; 79 else if(e == MOVE_TYPE::RIGHT && RUN(general_b.x,general_b.y+1)) yes = true; 80 if(!yes) break; // 对于黑主将每一种走法，只要此走法不会被将死，那么黑方目前未被将死 81 } 82 yes ? printf("YES\n") : printf("NO\n"); 83 } 84 return 0; 85 } 86 87 bool gensfight(Pos t){ 88 if(t.y != general_r.y) return false; // 如果两主将不在⼀条直线上直接否定 89 return others(general_r.x,t.x,t.y,TRAVERSE_TYPE::X) == 0; 90 } 91 bool RfightG(Pos t){for(auto &e : R){ // 将所有⻋遍历，看看它们上下左右是否直接与⿊⽅主将照⾯ 92 bool equalsX = ( e.x == t.x ), equalsY = ( e.y == t.y ); //直接照⾯的前提是它们⾄少在同⼀条直线上 93 if(!(equalsX || equalsY)) continue; // 如果此⻋不满⾜条件考虑下⼀个⻋ 94 if(equalsX){ 95 if(others(e.y,t.y,e.x,TRAVERSE_TYPE::Y) == 0) return true; 96 }else{ 97 if(others(e.x,t.x,e.y,TRAVERSE_TYPE::X) == 0) return true; 98 } 99 } 100 return false; 101 } 102 bool HfightG(Pos t){ // 将所有⻢遍历，看看它们是否直接踩到⿊⽅主将 103 for(auto &e : H){ // 只要有⼀匹⻢移动合法且直接踩到⿊主将则返回true 104 // validMoveH检查马的移动是否合法(包括蹩马脚、棋盘越界) 105 if(e.y-1 == t.y && e.x-2 == t.x && validMoveH(e.x,e.y,1)) return true; 106 if(e.y+1 == t.y && e.x-2 == t.x && validMoveH(e.x,e.y,2)) return true; 107 if(e.y-2 == t.y && e.x-1 == t.x && validMoveH(e.x,e.y,3)) return true; 108 if(e.y+2 == t.y && e.x-1 == t.x && validMoveH(e.x,e.y,4)) return true; 109 if(e.y-2 == t.y && e.x+1 == t.x && validMoveH(e.x,e.y,5)) return true; 110 if(e.y+2 == t.y && e.x+1 == t.x && validMoveH(e.x,e.y,6)) return true; 111 if(e.y-1 == t.y && e.x+2 == t.x && validMoveH(e.x,e.y,7)) return true; 112 if(e.y+1 == t.y && e.x+2 == t.x && validMoveH(e.x,e.y,8)) return true; 113 } 114 return false; // 程序控制流到达这里当且仅当所有存在的马均不能杀死黑主将 115 } 116 bool CfightG(Pos t){ // 将所有炮遍历，看看它们是否直接轰到⿊⽅主将 117 for(auto &e : H){ 118 bool equalsX = ( e.x == t.x ), equalsY = ( e.y == t.y ); // 炮打到⿊将的前提是它们⾄少在同⼀条直线上 119 if(!(equalsX || equalsY)) continue; // 如果此炮不满⾜条件考虑下⼀个炮 120 if(equalsX){ 121 int count = others(e.y,t.y,e.x,TRAVERSE_TYPE::Y); 122 if(count != 1) continue; // 考虑炮杀死黑主将的前提是它们之间仅有一个落子 123 else return true; // 只要有一个炮能做到即返回true 124 }else{ 125 int count = others(e.x,t.x,e.y,TRAVERSE_TYPE::X); 126 if(count == 0 || count > 1) continue;else return true; 127 } 128 } 129 return false; 130 } 131 int others(int begin,int end,int index,TRAVERSE_TYPE type){ 132 // 该函数计算同一直线上两落子之间落子的个数,index是指在遍历中固定不动的下标 133 if(begin > end) swap(begin,end); 134 int cnt = 0; 135 if(type == TRAVERSE_TYPE::X){ 136 for(int i = begin + 1;i < end;i ++) if(map[i][index]) cnt++; 137 }else{ // (type == TRAVERSE_TYPE::Y) 138 for(int i = begin + 1;i < end;i ++) if(map[index][i]) cnt++; 139 } 140 return cnt; 141 } 142 vector<MOVE_TYPE> validMoveG(){ 143 // 该函数将黑主将可走的方向放进一个临时vector并返回 144 vector<MOVE_TYPE> temp; 145 if(general_b.y != 4) temp.push_back(MOVE_TYPE::LEFT); 146 if(general_b.y != 6) temp.push_back(MOVE_TYPE::RIGHT); 147 if(general_b.x != 1) temp.push_back(MOVE_TYPE::UP); 148 if(general_b.x != 3) temp.push_back(MOVE_TYPE::DOWN); 149 return temp; 150 } 151 inline 152 bool RUN(int x,int y){ 153 // 该函数负责检查黑主将在每一种走法下是否会被一种存在类型的红方落子杀死 154 erasing(x,y); // 由于黑主将的下一个落点完全可能有一个红方棋子挡住，那么它可以直接吃掉也就是删除此落子 155 Pos t(x,y); 156 return RfightG(t) || HfightG(t) || CfightG(t) || gensfight(t); 157 } 158 bool validMoveH(int x,int y,int direct){ 159 if(direct==1){ // 这些map都代表会蹩马脚的位置，必须保证此位置没有落子 160 if(!(y-1 >= 1 && x-2 >= 1 && !map[x-1][y])) return false; 161 }else if(direct==2){ 162 if(!(y+1 <= 9 && x-2 >= 1 && !map[x-1][y])) return false; 163 }else if(direct==3){ 164 if(!(y-2 >= 1 && x-1 >= 1 && !map[x][y-1])) return false; 165 }else if(direct==4){ 166 if(!(y+2 <= 9 && x-1 >= 1 && !map[x][y+1])) return false; 167 }else if(direct==5){ 168 if(!(y-2 >= 1 && x+1 <= 10 && !map[x][y-1])) return false; 169 }else if(direct==6){ 170 if(!(y+2 <= 9 && x+1 <= 10 && !map[x][y+1])) return false; 171 }else if(direct==7){ 172 if(!(y-1 >= 1 && x+2 <= 10 && !map[x+1][y])) return false; 173 }else if(direct==8){ 174 if(!(y+1 <= 9 && x+2 <= 10 && !map[x+1][y])) return false; 175 } 176 return true; 177 } 178 void erasing(int x,int y){ 179 // 检查棋盘上(x,y)处落子的类型，如果存在即将它从它的集合中删除 180 if(mmap[x][y]=='R'){ 181 for(vector<Pos>::const_iterator it = R.begin();it != R.end();it 182 ++)if(it->x==x && it->y==y) R.erase(it); 183 }else if(mmap[x][y]=='H'){ 184 for(vector<Pos>::const_iterator it = H.begin();it != H.end();it 185 ++) 186 if(it->x==x && it->y==y) H.erase(it); 187 }else if(mmap[x][y]=='C'){ 188 for(vector<Pos>::const_iterator it = C.begin();it != C.end();it 189 ++) 190 if(it->x==x && it->y==y) C.erase(it); 191 } 192 }
