题意： 给一个象棋局势，问黑棋是否死棋了，黑棋只有一个将，红棋可能有2~7个棋，分别可能是车，马，炮以及帅。
解法： 开始写法是对每个棋子，都处理处他能吃的地方，赋为-1，然后判断将能不能走到非-1的点。但是WA了好久，也找不出反例，但就是觉得不行，因为可能有将吃子的情况，可能有hack点。但是比赛后还是被我调出来了。
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
using namespace std;
#define N 1017 int chess[][],mp[][]; //0 : Non 1:G帅 2:R车 3:H Horse 4:C Cannon
int dx[] = {,-,,};
int dy[] = {,,-,};
bool InPalace(int nx,int ny) { if(nx >= && nx <= && ny >= && ny <= ) return true; return false; }
bool InChess(int nx,int ny) { if(nx >= && nx <= && ny >= && ny <= ) return true; return false;} int main()
{
int n,X,Y,i,j,k;
int x,y;
char ss[];
while(scanf("%d%d%d",&n,&X,&Y)!=EOF && (n+X+Y))
{
memset(chess,,sizeof(chess));
memset(mp,,sizeof(mp));
for(i=;i<=n;i++)
{
//0 : Non 1:G帅 2:R车 3:H Horse 4:C Cannon
scanf("%s%d%d",ss,&x,&y);
if(ss[] == 'G') chess[x][y] = ;
else if(ss[] == 'R') chess[x][y] = ;
else if(ss[] == 'H') chess[x][y] = ;
else if(ss[] == 'C') chess[x][y] = ;
}
for(i=;i<=;i++)
{
for(j=;j<=;j++)
{
if(chess[i][j] == ) // shuai
{
for(k=i-;k>=;k--)
{
if(chess[k][j] != )
{
mp[k][j] = -;
break;
}
if(k <= && chess[k][j] == ) mp[k][j] = -;
}
}
else if(chess[i][j] == ) // R che
{
for(int D=;D<;D++)
{
int kx = i, ky = j;
while()
{
kx = kx + dx[D];
ky = ky + dy[D];
if(!InChess(kx,ky)) break;
if(chess[kx][ky] == ) mp[kx][ky] = -;
else
{
mp[kx][ky] = -;
break;
}
}
}
}
else if(chess[i][j] == ) //Horse
{
if(InChess(i-,j) && chess[i-][j] == && (i- != X || j != Y)) //UP not blocked
{
if(InChess(i-,j-)) mp[i-][j-] = -;
if(InChess(i-,j+)) mp[i-][j+] = -;
}
if(InChess(i+,j) && chess[i+][j] == && (i+ != X || j != Y)) //DOWN not blocked
{
if(InChess(i+,j-)) mp[i+][j-] = -;
if(InChess(i+,j+)) mp[i+][j+] = -;
}
if(InChess(i,j+) && chess[i][j+] == && (i != X || j+ != Y)) //RIGHT not blocked
{
if(InChess(i-,j+)) mp[i-][j+] = -;
if(InChess(i+,j+)) mp[i+][j+] = -;
}
if(InChess(i,j-) && chess[i][j-] == && (i != X || j- != Y)) //LEFT not blocked
{
if(InChess(i-,j-)) mp[i-][j-] = -;
if(InChess(i+,j-)) mp[i+][j-] = -;
}
}
else if(chess[i][j] == ) //Cannon pao
{
for(int D=;D<;D++)
{
int kx = i, ky = j;
int cnt = ;
while()
{
kx = kx + dx[D];
ky = ky + dy[D];
if(!InChess(kx,ky)) break;
if(cnt == && chess[kx][ky] == ) mp[kx][ky] = -;
if(chess[kx][ky] != )
{
if(cnt == ) cnt++;
else if(cnt == )
{
mp[kx][ky] = -;
break;
}
}
}
}
}
}
}
int tag = ;
for(k=;k<;k++)
{
int kx = X + dx[k];
int ky = Y + dy[k];
if(!InChess(kx,ky) || !InPalace(kx,ky)) continue;
if(mp[kx][ky] != -) { tag = ; break; } //可以走
}
if(tag) puts("NO");
else puts("YES");
}
return ;
}
比赛中后来换了一种写法，枚举将能走的四个位置，然后判断此时是否能被吃掉。 如果没有一个安全的地方，那么就死棋了。 这种写起来就好些多了。
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
#define N 1017 int chess[][],mp[][]; //0 : Non 1:G帅 2:R车 3:H Horse 4:C Cannon
int dx[] = {,-,,};
int dy[] = {,,-,}; bool InPalace(int nx,int ny)
{
if(nx >= && nx <= && ny >= && ny <= ) return true;
return false;
} bool InChess(int nx,int ny)
{
if(nx >= && nx <= && ny >= && ny <= ) return true;
return false;
} struct node{
int x,y,type;
}q[]; bool Check(int X,int Y,int i,int j,int type) //将死则 return false !
{
int k;
if(type == ) //帅
{
if(j != Y) return true; //不是一行
for(k=i-;k>X;k--)
{
if(chess[k][j] != )
break;
}
if(k == X) return false; //老倌子见面,gg
return true;
}
else if(type == ) //R
{
int tag = ;
for(int D=;D<;D++)
{
int kx = i, ky = j;
while()
{
kx = kx + dx[D];
ky = ky + dy[D];
if(!InChess(kx,ky)) break;
if(kx == X && ky == Y) //车能碰到将
{
tag = ;
break;
}
if(chess[kx][ky] != )
break;
}
}
if(!tag) return false;
return true;
}
else if(type == ) //Horse
{
int tag = ;
if(InChess(i-,j) && chess[i-][j] == && (i- != X && j != Y)) //UP not blocked
{
if(InChess(i-,j-) && i- == X && j- == Y)
tag = ;
if(InChess(i-,j+) && i- == X && j+ == Y)
tag = ;
}
if(InChess(i+,j) && chess[i+][j] == && (i+ != X && j != Y)) //DOWN not blocked
{
if(InChess(i+,j-) && i+ == X && j- == Y)
tag = ;
if(InChess(i+,j+) && i+ == X && j+ == Y)
tag = ;
}
if(InChess(i,j+) && chess[i][j+] == && (i != X && j+ != Y)) //RIGHT not blocked
{
if(InChess(i-,j+) && i- == X && j+ == Y)
tag = ;
if(InChess(i+,j+) && i+ == X && j+ == Y)
tag = ;
}
if(InChess(i,j-) && chess[i][j-] == && (i != X && j- != Y)) //LEFT not blocked
{
if(InChess(i-,j-) && i- == X && j- == Y)
tag = ;
if(InChess(i+,j-) && i+ == X && j- == Y)
tag = ;
}
if(!tag) return false;
return true;
}
else if(type == ) //Cannon
{
int tag = ;
for(int D=;D<;D++)
{
int kx = i, ky = j;
int cnt = ;
while()
{
kx = kx + dx[D];
ky = ky + dy[D];
if(!InChess(kx,ky)) break;
if(cnt == && kx == X && ky == Y)
{
tag = ;
break;
}
if(chess[kx][ky] != )
cnt++;
}
}
if(!tag) return false;
return true;
}
return false;
} int main()
{
int n,X,Y,i,j,k;
int x,y;
char ss[];
while(scanf("%d%d%d",&n,&X,&Y)!=EOF && (n+X+Y))
{
memset(chess,,sizeof(chess));
int tot = ;
for(i=;i<=n;i++)
{
//0 : Non 1:G帅 2:R车 3:H Horse 4:C Cannon
scanf("%s %d%d",ss,&x,&y);
if(ss[] == 'G')
chess[x][y] = ;
else if(ss[] == 'R')
chess[x][y] = ;
else if(ss[] == 'H')
chess[x][y] = ;
else if(ss[] == 'C')
chess[x][y] = ;
node now;
now.x = x, now.y = y, now.type = chess[x][y];
q[++tot] = now;
}
int flag[];
int tag = ;
for(k=;k<;k++)
{
int nx = X + dx[k];
int ny = Y + dy[k];
memset(flag,,sizeof(flag));
if(!InChess(nx,ny) || !InPalace(nx,ny)) continue;
for(i=;i<=tot;i++)
{
if(nx == q[i].x && ny == q[i].y)
{
flag[i] = ;
chess[nx][ny] = ;
}
}
int smalltag = ;
for(i=;i<=tot;i++)
{
if(flag[i]) continue;
bool res = Check(nx,ny,q[i].x,q[i].y,q[i].type);
if(!res) { smalltag = ; break; }
}
if(smalltag)
{
tag = ;
break;
}
// 还原
for(i=;i<=tot;i++)
{
if(flag[i])
chess[q[i].x][q[i].y] = q[i].type;
}
}
if(tag) puts("NO");
else puts("YES");
}
return ;
}