大榕树 \ 信息学奥赛 \ 网上竞赛

《神奇国度》参考程序

原文链接：http://www.mydrs.org/program/list.asp?id=434

试题： 神奇国度。 （20分）
在一个神奇的国度里，住着许多象和马。但是象和马都是脾气暴躁的动物，他们严禁别人踏入自己的领地。一但有动物找到了合适的并且没有占领的土地，他们就会在那里栖息下来，并且把一定的土地划为己有（当然，土地必须在这个国度内），别的动物就不能到他的领地里来了。
我们可以把这个国度看成是 n*m 的矩阵（1<=n,m<=20）。当象占领(x,y)这个点后，(x+2,y+2)、(x+2,y-2)、(x-2,y+2)、(x-2,y-2)以及他自身所在的点就是他的领地了。当马占领(x,y)这个点后，(x+1,y+1)、(x+1,y-1)、(x-1,y+1)、(x-1,y-1)以及他自身所在的点就是他的领地了。</P><P>试问，这个国度最多能供多少个动物栖息？</P><P>输入格式：n m 1<=n,m<=10 (input2.txt)</P><P>输出格式：S1 (output2.txt)</P><P>例如： 输入 3 3
输出 7</P><P>
{$A+,B-,D-,E+,F-,G+,I-,L+,N+,O-,P+,Q+,R-,S-,T+,V+,X+}
{$M 65520,0,655360}
type
    usetype=array[-1..22,-1..22]of boolean;
var
   n,m:longint;
   use:usetype;
   max,now:longint;
   f:array[0..20]of longint;
   km:array[1..20,1..20]of longint;
procedure init;
begin
     assign(input,'input2.txt');
     reset(input);
     read(n,m);
     close(input);
     fillchar(use,sizeof(use),0);
end;
function can(x,y,j:longint):boolean;
begin
     if (use[x+j,y+j])and(x+j<=n)and(y+j<=m) then begin can:=false; exit; end;
     if (use[x+j,y-j])and(x+j<=n)and(y-j>=1) then begin can:=false; exit; end;
     if (use[x-j,y+j])and(x+j>=1)and(y+j<=m) then begin can:=false; exit; end;
     if (use[x-j,y-j])and(x+j>=1)and(y-j>=1) then begin can:=false; exit; end;
     can:=true;
end;
procedure try(x,y,now:longint);
var
   i,j,k,nx,ny:longint;
   tuse:usetype;
begin
     if now>km[x,y] then km[x,y]:=now;
     if now+m div 3<km[x,y] then exit;
     if now>f[n] then f[n]:=now;
     if (x=n)and(y>m) then exit;
     if (now+m-y+1)+m div 5<f[x] then exit;
     if f[n-x]+now+m-y+1<f[n] then exit;
     if y=m then
        begin
             if x<>n then begin nx:=x+1; ny:=1; end else begin nx:=x; ny:=y+1; end;
             for i:=x to n do if now>f[i] then f[i]:=now else break;
        end else
        begin
         nx:=x; ny:=y+1;
        end;
     if use[x,y]=false then
     begin
          for j:=1 to 2 do
          if can(x,y,j) then
          begin
               tuse:=use;
               use[x,y]:=true; use[x+j,y+j]:=true; use[x+j,y-j]:=true;
               use[x-j,y+j]:=true; use[x-j,y-j]:=true;
               try(nx,ny,now+1);
               use:=tuse;
          end;
     end;
     try(nx,ny,now);
end;
begin
     init;
     fillchar(f,sizeof(f),0);
     fillchar(km,sizeof(km),0);
     now:=0;
     try(1,1,now);
     assign(output,'output2.txt');
     rewrite(output);
     writeln(f[n]);
     close(output);
end.

作者：Fruit
来源：
时间：2002-10-10

上一篇：《硬币找零》参考程序
下一篇：分区初赛模拟卷选择题

大榕树 版权所有 ©1999-2006