POJ2044 Weather Forecast — BFS+状态简化

Note: 本文最初于 2011年02月27日 星期日 21:43 在 hi.baidu.com/lydrainbowcat 发表。š

题意：有一朵2*2的云朵，和一个4*4的地区。被云层覆盖的区域在当天一定有雨下，云层有4种移动方式 。已知N天内的节日日期，希望在这N天内，节日期间不要下雨，并且每个地方不能连续7天不下雨。问能否满足上述要求？

解法：š分析发现，只要4*4的地区中，四个角在6天内都下过雨，那么其它地方肯定也下过雨。

š因此只需在状态中记录：当前日期、云朵位置、四个角上次下雨分别是在几天前，BFS搜索每天云朵的移动方式，最终检查N天后是否存在合法的状态即可。

Source Code

Problem: 2044		User: lydliyudong
Memory: 25584K		Time: 516MS
Language: Pascal		Result: Accepted

• Source Code

var
 a:array[1..365,1..4,1..4]of integer;
 f:array[1..365,1..4,1..4,0..6,0..6,0..6,0..6]of boolean;
 q:array[0..1000000]of integer;
 s:array[0..1000000]of ansistring;
 n,i,j,k,l,r:longint;
 suc:boolean;

procedure applepi(x,y,r1,r2,r3,r4:longint);
 begin
  if (x<1)or(y<1)or(x>3)or(y>3)or suc then exit;
  if (a[q[l]+1,x,y]=1)or(a[q[l]+1,x,y+1]=1)or(a[q[l]+1,x+1,y]=1)or(a[q[l]+1,x+1,y+1]=1) then exit;
  inc(r1); inc(r2); inc(r3); inc(r4);
  if (x=1)and(y=1) then r1:=0;
  if (x=1)and(y=3) then r2:=0;
  if (x=3)and(y=1) then r3:=0;
  if (x=3)and(y=3) then r4:=0;
  if (r1=7)or(r2=7)or(r3=7)or(r4=7)or f[q[l]+1,x,y,r1,r2,r3,r4] then exit;
  if q[l]+1=n then begin suc:=true; exit; end;
  inc(r);
  q[r]:=q[l]+1;
  s[r]:=chr(x+ord('0'))+chr(y+ord('0'))+chr(r1+ord('0'))+chr(r2+ord('0'))+chr(r3+ord('0'))+chr(r4+ord('0'));
  f[q[r],x,y,r1,r2,r3,r4]:=true;
 end;

function bfsdp:boolean;
 var
  x,y,r1,r2,r3,r4:longint;
 begin
  l:=1; r:=1;
  q[1]:=1; s[1]:='221111';
  if (a[q[l],2,2]=1)or(a[q[l],2,3]=1)or(a[q[l],3,2]=1)or(a[q[l],3,3]=1) then exit(false);
  while l<=r do
   begin
    x:=ord(s[l,1])-ord('0');
    y:=ord(s[l,2])-ord('0');
    r1:=ord(s[l,3])-ord('0');
    r2:=ord(s[l,4])-ord('0');
    r3:=ord(s[l,5])-ord('0');
    r4:=ord(s[l,6])-ord('0');
    applepi(x,y,r1,r2,r3,r4);
    applepi(x-2,y,r1,r2,r3,r4);
    applepi(x-1,y,r1,r2,r3,r4);
    applepi(x+1,y,r1,r2,r3,r4);
    applepi(x+2,y,r1,r2,r3,r4);
    applepi(x,y-2,r1,r2,r3,r4);
    applepi(x,y-1,r1,r2,r3,r4);
    applepi(x,y+1,r1,r2,r3,r4);
    applepi(x,y+2,r1,r2,r3,r4);
    if suc then exit(true);
    inc(l);
   end;
  exit(false);
 end;

begin
 repeat
  readln(n);
  if n=0 then break;
  fillchar(f,sizeof(f),0);
  suc:=false;
  for i:=1 to n do for j:=1 to 4 do for k:=1 to 4 do read(a[i,j,k]);
  if bfsdp then writeln(1) else writeln(0);
 until seekeof;
end.