Xiangqi
Time Limit: 20 Sec
Memory Limit: 256 MB
题目连接
http://acm.hdu.edu.cn/showproblem.php?pid=4121
Description
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
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
HINT
题意
给你一个象棋残局，黑方只剩下一个王了。现在该王走了，是否王怎么走都会死了？
题解：
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[]={,-,,};
int dy[]={,,,-};
int vis[][];
void init()
{
P.clear();
H.clear();
C.clear();
G.clear();
memset(vis,,sizeof(vis));
}
int check(int xx,int yy)
{
//cout<<xx<<" "<<yy<<endl;
if(xx<||xx>)return ;
if(yy<||yy>)return ; for(int i=;i<C.size();i++)
{
int xxx = C[i].first, yyy = C[i].second;
if(xxx == xx && yyy == yy)
continue;
while(xxx<=)
{
xxx++;
if(xxx == xx && yyy == yy)
return ;
if(vis[xxx][yyy])
break;
}
xxx = C[i].first, yyy = C[i].second;
while(xxx)
{
xxx--;
if(xxx == xx && yyy == yy)
return ;
if(vis[xxx][yyy])
break;
}
xxx = C[i].first, yyy = C[i].second;
while(yyy<=)
{
yyy++;
if(xxx == xx && yyy == yy)
return ;
if(vis[xxx][yyy])
break;
}
xxx = C[i].first, yyy = C[i].second;
while(yyy)
{
yyy--;
if(xxx == xx && yyy == yy)
return ;
if(vis[xxx][yyy])
break;
}
}
//cout<<xx<<" "<<yy<<endl;
for(int i=;i<H.size();i++)
{
int xxx = H[i].first , yyy = H[i].second;
if(xxx == xx && yyy == yy)
continue;
if(xxx != && vis[xxx-][yyy]==)
{
if(xx == xxx - && yy == yyy + )
return ;
if(xx == xxx - && yy == yyy - )
return ;
}
if(xxx != && vis[xxx+][yyy]==)
{
if(xx == xxx + && yy == yyy + )
return ;
if(xx == xxx + && yy == yyy - )
return ;
}
if(yyy != && vis[xxx][yyy-]==)
{
if(xx == xxx + && yy == yyy - )
return ;
if(xx == xxx - && yy == yyy - )
return ;
}
if(yyy != && vis[xxx][yyy+]==)
{
if(xx == xxx + && yy == yyy + )
return ;
if(xx == xxx - && yy == yyy + )
return ;
}
}
//cout<<xx<<" "<<yy<<endl;
for(int i=;i<P.size();i++)
{
int xxx = P[i].first,yyy = P[i].second;
if(xxx == xx && yyy == yy)
continue;
int flag = ;
while(xxx<=)
{
xxx++;
if(xxx == xx && yyy == yy && flag == )
return ;
if(vis[xxx][yyy])
flag++;
}
xxx = P[i].first, yyy = P[i].second,flag = ;
while(xxx)
{
xxx--;
if(xxx == xx && yyy == yy && flag == )
return ;
if(vis[xxx][yyy])
flag++;
}
xxx = P[i].first, yyy = P[i].second,flag = ;
while(yyy<=)
{
yyy++;
if(xxx == xx && yyy == yy && flag == )
return ;
if(vis[xxx][yyy])
flag++;
}
xxx = P[i].first, yyy = P[i].second,flag = ;
while(yyy)
{
yyy--;
if(xxx == xx && yyy == yy && flag == )
return ;
if(vis[xxx][yyy])
flag++;
}
} for(int i=;i<G.size();i++)
{
int xxx = G[i].first, yyy = G[i].second;
if(xxx == xx && yyy == yy)
continue;
while(xxx<=)
{
xxx++;
if(xxx == xx && yyy == yy)
return ;
if(vis[xxx][yyy])
break;
}
xxx = G[i].first, yyy = G[i].second;
while(xxx)
{
xxx--;
if(xxx == xx && yyy == yy)
return ;
if(vis[xxx][yyy])
break;
}
xxx = G[i].first, yyy = G[i].second;
while(yyy<=)
{
yyy++;
if(xxx == xx && yyy == yy)
return ;
if(vis[xxx][yyy])
break;
}
xxx = G[i].first, yyy = G[i].second;
while(yyy)
{
yyy--;
if(xxx == xx && yyy == yy)
return ;
if(vis[xxx][yyy])
break;
}
}
//cout<<xx<<" "<<yy<<endl;
return ;
}
int main()
{
while(scanf("%d%d%d",&n,&x,&y)!=EOF)
{
if(n== && x == && y == )
break;
init();
string cc;int xx,yy;
for(int i=;i<n;i++)
{
cin>>cc;
scanf("%d %d",&xx,&yy);
if(cc[]=='G')
G.push_back(make_pair(xx,yy));
if(cc[]=='R')
C.push_back(make_pair(xx,yy));
if(cc[]=='H')
H.push_back(make_pair(xx,yy));
if(cc[]=='C')
P.push_back(make_pair(xx,yy));
vis[xx][yy]++;
} xx = x,yy = y;
int flag2 = ;
for(int i=;i<G.size();i++)
{
int xxx = G[i].first, yyy = G[i].second;
if(xxx == xx && yyy == yy)
continue;
while(xxx<=)
{
xxx++;
if(xxx == xx && yyy == yy)
flag2 = ;
if(vis[xxx][yyy])
break;
}
xxx = G[i].first, yyy = G[i].second;
while(xxx)
{
xxx--;
if(xxx == xx && yyy == yy)
flag2 = ;
if(vis[xxx][yyy])
break;
}
xxx = G[i].first, yyy = G[i].second;
while(yyy<=)
{
yyy++;
if(xxx == xx && yyy == yy)
flag2 = ;
if(vis[xxx][yyy])
break;
}
xxx = G[i].first, yyy = G[i].second;
while(yyy)
{
yyy--;
if(xxx == xx && yyy == yy)
flag2 = ;
if(vis[xxx][yyy])
break;
}
}
if(flag2)
{
printf("NO\n");
continue;
}
int flag = ;
for(int i=;i<;i++)
{
xx = x + dx[i];
yy = y + dy[i];
vis[xx][yy]++;
if(!check(xx,yy))
flag ++;
vis[xx][yy]--;
}
if(flag == )
printf("YES\n");
else
printf("NO\n");
}
}