Time Limit: 20 Sec
Memory Limit: 256 MB
http://acm.hdu.edu.cn/showproblem.php?pid=4121
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”.
Input
Output
For each test case, if the situation is checkmate, output a single word ‘YES’, otherwise output the word ‘NO’.
Sample Input
2 1 4
G 10 5
R 6 4
3 1 5
H 4 5
G 10 5
C 7 5
0 0 0
Sample Output
YES
NO
题意
给你一个象棋残局，黑方只剩下一个王了。现在该王走了，是否王怎么走都会死了？
题解：
1.黑方王在走的时候，可以踩死红方棋子
2.马会被蹩脚
然后没有什么坑点了，暴力模拟就好了……
代码
#include<iostream> #include<stdio.h> #include<vector> #include<cstring> using namespace std; int n,x,y; vector<pair<int,int> >P; vector<pair<int,int> >H; vector<pair<int,int> >C; vector<pair<int,int> >G; int dx[4]={1,-1,0,0}; int dy[4]={0,0,1,-1}; int vis[15][15]; void init() { P.clear(); H.clear(); C.clear(); G.clear(); memset(vis,0,sizeof(vis)); } int check(int xx,int yy) { //cout<<xx<<" "<<yy<<endl; if(xx<1||xx>3)return 1; if(yy<4||yy>6)return 1; for(int i=0;i<C.size();i++) { int xxx = C[i].first, yyy = C[i].second; if(xxx == xx && yyy == yy) continue; while(xxx<=10) { xxx++; if(xxx == xx && yyy == yy) return 1; if(vis[xxx][yyy]) break; } xxx = C[i].first, yyy = C[i].second; while(xxx) { xxx--; if(xxx == xx && yyy == yy) return 1; if(vis[xxx][yyy]) break; } xxx = C[i].first, yyy = C[i].second; while(yyy<=9) { yyy++; if(xxx == xx && yyy == yy) return 1; if(vis[xxx][yyy]) break; } xxx = C[i].first, yyy = C[i].second; while(yyy) { yyy--; if(xxx == xx && yyy == yy) return 1; if(vis[xxx][yyy]) break; } } //cout<<xx<<" "<<yy<<endl; for(int i=0;i<H.size();i++) { int xxx = H[i].first , yyy = H[i].second; if(xxx == xx && yyy == yy) continue; if(xxx != 1 && vis[xxx-1][yyy]==0) { if(xx == xxx - 2 && yy == yyy + 1) return 1; if(xx == xxx - 2 && yy == yyy - 1) return 1; } if(xxx != 10 && vis[xxx+1][yyy]==0) { if(xx == xxx + 2 && yy == yyy + 1) return 1; if(xx == xxx + 2 && yy == yyy - 1) return 1; } if(yyy != 1 && vis[xxx][yyy-1]==0) { if(xx == xxx + 1 && yy == yyy - 2) return 1; if(xx == xxx - 1 && yy == yyy - 2) return 1; } if(yyy != 9 && vis[xxx][yyy+1]==0) { if(xx == xxx + 1 && yy == yyy + 2) return 1; if(xx == xxx - 1 && yy == yyy + 2) return 1; } } //cout<<xx<<" "<<yy<<endl; for(int i=0;i<P.size();i++) { int xxx = P[i].first,yyy = P[i].second; if(xxx == xx && yyy == yy) continue; int flag = 0; while(xxx<=10) { xxx++; if(xxx == xx && yyy == yy && flag == 1) return 1; if(vis[xxx][yyy]) flag++; } xxx = P[i].first, yyy = P[i].second,flag = 0; while(xxx) { xxx--; if(xxx == xx && yyy == yy && flag == 1) return 1; if(vis[xxx][yyy]) flag++; } xxx = P[i].first, yyy = P[i].second,flag = 0; while(yyy<=9) { yyy++; if(xxx == xx && yyy == yy && flag == 1) return 1; if(vis[xxx][yyy]) flag++; } xxx = P[i].first, yyy = P[i].second,flag = 0; while(yyy) { yyy--; if(xxx == xx && yyy == yy && flag == 1) return 1; if(vis[xxx][yyy]) flag++; } } for(int i=0;i<G.size();i++) { int xxx = G[i].first, yyy = G[i].second; if(xxx == xx && yyy == yy) continue; while(xxx<=10) { xxx++; if(xxx == xx && yyy == yy) return 1; if(vis[xxx][yyy]) break; } xxx = G[i].first, yyy = G[i].second; while(xxx) { xxx--; if(xxx == xx && yyy == yy) return 1; if(vis[xxx][yyy]) break; } xxx = G[i].first, yyy = G[i].second; while(yyy<=9) { yyy++; if(xxx == xx && yyy == yy) return 1; if(vis[xxx][yyy]) break; } xxx = G[i].first, yyy = G[i].second; while(yyy) { yyy--; if(xxx == xx && yyy == yy) return 1; if(vis[xxx][yyy]) break; } } //cout<<xx<<" "<<yy<<endl; return 0; } int main() { while(scanf("%d%d%d",&n,&x,&y)!=EOF) { if(n==0 && x == 0 && y == 0) break; init(); string cc;int xx,yy; for(int i=0;i<n;i++) { cin>>cc; scanf("%d %d",&xx,&yy); if(cc[0]==‘G‘) G.push_back(make_pair(xx,yy)); if(cc[0]==‘R‘) C.push_back(make_pair(xx,yy)); if(cc[0]==‘H‘) H.push_back(make_pair(xx,yy)); if(cc[0]==‘C‘) P.push_back(make_pair(xx,yy)); vis[xx][yy]++; } xx = x,yy = y; int flag2 = 0; for(int i=0;i<G.size();i++) { int xxx = G[i].first, yyy = G[i].second; if(xxx == xx && yyy == yy) continue; while(xxx<=10) { xxx++; if(xxx == xx && yyy == yy) flag2 = 1; if(vis[xxx][yyy]) break; } xxx = G[i].first, yyy = G[i].second; while(xxx) { xxx--; if(xxx == xx && yyy == yy) flag2 = 1; if(vis[xxx][yyy]) break; } xxx = G[i].first, yyy = G[i].second; while(yyy<=9) { yyy++; if(xxx == xx && yyy == yy) flag2 = 1; if(vis[xxx][yyy]) break; } xxx = G[i].first, yyy = G[i].second; while(yyy) { yyy--; if(xxx == xx && yyy == yy) flag2 = 1; if(vis[xxx][yyy]) break; } } if(flag2) { printf("NO\n"); continue; } int flag = 0; for(int i=0;i<4;i++) { xx = x + dx[i]; yy = y + dy[i]; vis[xx][yy]++; if(!check(xx,yy)) flag ++; vis[xx][yy]--; } if(flag == 0) printf("YES\n"); else printf("NO\n"); } }
原文：http://www.cnblogs.com/qscqesze/p/4918284.html