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.

评论

0条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据