POJ 4001(Xiangqi-大模拟)
ICPC Fuzhou regional 2011, UVA 1589, hdu 4121
整理blog时发现一堆没发出去的草稿……
回顾了下Pascal，和2011 icpc regional
Xiangqi
这是一个中国象棋（Xiangqi）的残局判定问题。
棋盘与棋子：
- 棋盘为 10 行 9 列，坐标从 (1,1) 到 (10,9)。
- 本题只涉及 4 种棋子：将(G)、车®、炮©、马(H)。
- 红方已“将军”，现在轮到黑方走棋。
核心问题：
给定一个局面（包含一个黑将、一个红帅以及若干红方棋子），判断当前是否为“将死”（Checkmate）。
将死的定义：
黑将无法通过任何一步合法的移动（上下左右，且不出九宫）来避免在下一步被红方棋子吃掉。
输入：
多组数据，直到0 0 0。
每组第一行：N Bx By(红子数量 N，黑将位置 Bx, By)。
接下来 N 行：每行一个字符（棋子类型 G/R/C/H）和两个整数（棋子坐标）。
数据保证局面合法，且红方已将军。
输出：
对于每组数据，如果是将死，输出"YES"，否则输出"NO"。
本题是大模拟。注意黑方必须移动棋子，且移动后有可能吃了红方的一个棋子。
稍微试了下csdn自带的ai优化，感觉还行
Program P4001; Var n,x,y,i,j,x1,y1,yredg:longint; c:char; map:array[-100..100,-100..100] of longint; fx,fy:array[1..100] of longint; Function solve(x,y:longint):boolean; //weather red win var i,j,p,sum,xd,yd,tmp:longint; begin solve:=false; tmp:=map[x,y]; map[x,y]:=0; for i:=1 to n do begin p:=map[fx[i],fy[i]]; if p=2 then begin sum:=0; if fx[i]=x then begin if fy[i]<y then for j:=fy[i]+1 to y-1 do inc(sum,map[x,j]); if fy[i]>y then for j:=y+1 to fy[i]-1 do inc(sum,map[x,j]); if (sum=0) then solve:=true; end else if fy[i]=y then begin if fx[i]<x then for j:=fx[i]+1 to x-1 do inc(sum,map[j,y]); if fx[i]>x then for j:=x+1 to fx[i]-1 do inc(sum,map[j,y]); if (sum=0) then solve:=true; end; end; if p=3 then begin sum:=0; if fx[i]=x then begin if fy[i]<y then for j:=fy[i]+1 to y-1 do if map[x,j]>0 then inc(sum); if fy[i]>y then for j:=y+1 to fy[i]-1 do if map[x,j]>0 then inc(sum); if (sum=1) then solve:=true; end else if fy[i]=y then begin if fx[i]<x then for j:=fx[i]+1 to x-1 do if map[j,y]>0 then inc(sum); if fx[i]>x then for j:=x+1 to fx[i]-1 do if map[j,y]>0 then inc(sum); if (sum=1) then solve:=true; end; end; if p=4 then begin xd:=x-fx[i]; yd:=y-fy[i]; if (xd<>0) and (yd<>0) then begin if (xd=-1) and (yd=-2) then if map[x+1,y+1]=0 then solve:=true; if (xd=-2) and (yd=-1) then if map[x+1,y+1]=0 then solve:=true; if (xd=1) and (yd=2) then if map[x-1,y-1]=0 then solve:=true; if (xd=2) and (yd=1) then if map[x-1,y-1]=0 then solve:=true; if (xd=1) and (yd=-2) then if map[x-1,y+1]=0 then solve:=true; if (xd=2) and (yd=-1) then if map[x-1,y+1]=0 then solve:=true; if (xd=-1) and (yd=2) then if map[x+1,y-1]=0 then solve:=true; if (xd=-2) and (yd=1) then if map[x+1,y-1]=0 then solve:=true; end; end; end; map[x,y]:=tmp; end; function main:boolean; //weather checkmate var i,j:longint; begin main:=true; if y>4 then if not(solve(x,y-1)) then main:=false; if y<6 then if not(solve(x,y+1)) then main:=false; if x>1 then if not(solve(x-1,y)) then main:=false; if x<3 then if not(solve(x+1,y)) then main:=false; end; Begin readln(n,x,y); while (n+x+y>0) do begin fillchar(map,sizeof(map),0); for i:=1 to n do begin read(c); while (c<>'G') and (c<>'R') and (c<>'C') and (c<>'H') do read(c); readln(x1,y1); fx[i]:=x1; fy[i]:=y1; if c='G' then map[x1,y1]:=2 else if c='R' then map[x1,y1]:=2 else if c='C' then map[x1,y1]:=3 else if c='H' then map[x1,y1]:=4; end; if main then writeln('YES') else writeln('NO'); readln(n,x,y); end; End.