HDU 4121 Xiangqi 模拟题
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");
}
}
最新文章
- C语言 &#183; 4-3水仙花数
- 数据库执行sql报错Got a packet bigger than &#39;max_allowed_packet&#39; bytes及重启mysql
- eval 与 Function
- 在SQL中取出字符串中数字部分或在SQL中取出字符部分
- aspose.cell 自定义模板 SUM无效
- static和public
- C++:类的创建
- InnoDB的redo日志管理---饶珑辉
- BZOJ 1997: [Hnoi2010]Planar( 2sat )
- 想精度高,可以考虑用c语言中的函数gettimeofday
- 1.C#基础学习笔记3---C#字符串(转义符和内存存储无关)
- Ubuntu Intel显卡驱动安装 (Ubuntu 14.04--Ubuntu 16.10 + Intel&#174; Graphics Update Tool)
- boot+Xss防攻击的处理方案
- ZeroMQ总结
- /usr/bin/ld: 找不到 -lmsc----解决方案
- beta冲刺————第一天(1/5)
- AT24Cxx(EEPROM)子系统
- js的mime类型有哪些?
- TSQL--按某字段列分组,在将各组中某列合并成一行
- MySQL(视图、触发器、函数)
热门文章
- java classpath、path用法
- 通过js检测到iframe,使父窗口重定向到index	-----------???----------------------
- Python easy_install
- C# 如何以参数的形式调用.exe程序
- C# delegate 学习 (练这么久终于悟出来点东东了,继续加油! ^_^)
- awk简单使用『摘.非原创』
- 【LeetCode 160】Intersection of Two Linked Lists
- T-SQL 数据库笔试题
- U盘安装Centos5.3
- php环境配置中各个模块在网站建设中的功能