hdu3514:Queen’s Case【极大极小搜索】
这题真是够坑的了。。。
题目大意:在一个地图里,有一个皇后(Q)还有一个军队(A)(虽然我觉得翻译成士兵比较靠谱)和若干个出口(E),当然地图里还会有障碍物(#)。这个游戏是回合制,每个回合皇后和士兵各移动一步,可以向周围四个方向移动一格或者原地不动,如果在一个回合结束后皇后到了出口而军队没有到同一个格子那么皇后就能成功逃脱,如果回合结束时皇后和军队在同一个格子(即使是出口)那么皇后就会被抓住。当然还会有双方谁都无法获胜的情况。那么在双方都使用最佳策略的时候游戏结果会如何呢?
这题很典型是一个极大极小博弈,用搜索就可以解决。虽然说一般极大极小搜索都是DFS,但这题用BFS会好一点(因为有死循环的情况不太方便处理)。
极大极小搜索是从初始状态逐步搜索到结束状态,然后每一次向下搜索要交换先后手(也就是说搜一步最大值,再搜一步最小值),通过alpha-beta剪枝来进行优化。然而这题如果从开始状态搜索,会出现死循环,这样几乎没法处理DFS的各种情况。所以我们可以先预处理所有结束的状态,然后把所有的可能情况存储下来,最后再倒着往回推。
考虑到棋盘最大也就30*30,那么可以用
f[0..1,i,j,k,l]表示在皇后回合(1)和在军队回合(0),皇后在(i,j),军队在(k,l)的时候的结果,其中用1表示军队必胜,用-1表示皇后必胜,0代表没有搜索到(也就是死循环,至于为什么待会解释)。
首先是预处理,也就是把所有结束的状态搜一遍,这个很好弄:
1、如果在皇后的回合,皇后和军队在一个格子,那么军队必胜。
2、如果在军队的回合,皇后离军队只有一格远,那么军队必胜。
3、如果在军队的回合,皇后离军队的距离大于一,并且皇后在某个出口,那么皇后必胜。
然后就倒着推,其实对于双方都是一样的策略:
1、如果当前走一步能到必胜的状态,那么当前状态必胜。
2、如果当前怎么都都是必败的状态,那么当前状态必败。
然后就类似于BFS不断扩展状态知道不能扩展为止,如果搜索结束后某个状态的值还是0的话说明这个状态不会有赢家。
然后几个注意点(虽然我觉得放前面一点会好一些):
1、“一个回合”指的是皇后移动一次,军队移动一次。也就是说皇后走一步到出口还得等军队走一步,然后再判定皇后是否被抓住。
2、题目有多组数据。
3、题目有多组数据。
4、题目有多组数据。(重要的事情说三遍,我才不会说我每组数据忘了fillchar呢)。
代码:
const fx:array[1..5,1..2] of longint=((1,0),(-1,0),(0,1),(0,-1),(0,0)); var f:array[0..1,1..30,1..30,1..30,1..30] of longint; a:array[1..30,1..30] of char; n,m,i,j,k,l,x,y,xx,yy,ax,ay,qx,qy,turn,t:longint; flag,b:boolean; function ok(x,y:longint):boolean; begin exit((x>0) and (x<=n) and (y>0) and (y<=m) and (a[x,y]<>'#')); end; begin while not eof do begin fillchar(f,sizeof(f),0); readln(m,n); for i:=1 to n do begin for j:=1 to m do begin read(a[i,j]); if a[i,j]='E' then begin for k:=1 to 5 do begin xx:=i+fx[k,1]; yy:=j+fx[k,2]; if ok(xx,yy) then f[0,i,j,xx,yy]:=1; end; for k:=1 to n do for l:=1 to m do if f[0,i,j,k,l]=0 then f[0,i,j,k,l]:=-1; end; if a[i,j]='A' then begin ax:=i; ay:=j; end; if a[i,j]='Q' then begin qx:=i; qy:=j; end; f[0,i,j,i,j]:=1; f[1,i,j,i,j]:=1; end; readln; end; for i:=1 to n do for j:=1 to m do for k:=1 to 5 do begin xx:=i+fx[k,1]; yy:=j+fx[k,2]; if ok(xx,yy) then f[0,i,j,xx,yy]:=1; end; flag:=true; turn:=1; while flag do begin flag:=false; for i:=1 to n do for j:=1 to m do if ok(i,j) then begin for k:=1 to n do for l:=1 to m do if ok(k,l) and (f[turn,i,j,k,l]=0) then if turn=1 then begin b:=true; for t:=1 to 5 do begin xx:=i+fx[t,1]; yy:=j+fx[t,2]; if ok(xx,yy) then begin if f[0,xx,yy,k,l]=-1 then begin f[1,i,j,k,l]:=-1; flag:=true; break; end else if f[0,xx,yy,k,l]=0 then b:=false; end; end; if b and (f[1,i,j,k,l]=0) then begin f[1,i,j,k,l]:=1; flag:=true; end; end else begin b:=true; for t:=1 to 5 do begin xx:=k+fx[t,1]; yy:=l+fx[t,2]; if ok(xx,yy) then begin if f[1,i,j,xx,yy]=1 then begin f[0,i,j,k,l]:=1; flag:=true; break; end else if f[1,i,j,xx,yy]=0 then b:=false; end; end; if b and (f[0,i,j,k,l]=0) then begin f[0,i,j,k,l]:=-1; flag:=true; end; end; end; if f[1,qx,qy,ax,ay]<>0 then break; turn:=turn xor 1; end; if f[1,qx,qy,ax,ay]=1 then writeln('Army can catch Queen.'); if f[1,qx,qy,ax,ay]=0 then writeln('Queen can not escape and Army can not catch Queen.'); if f[1,qx,qy,ax,ay]=-1 then writeln('Queen can escape.'); end; end.
发表回复