注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

z55250825

一只蒟蒻

 
 
 

日志

 
 

【BZOJ1054】【HAOI2008】【移动玩具】  

2014-03-17 15:59:13|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
   “请问一下小z您对HAOI2008及其以前的看法可以吗?”
   “咱可以吐槽一些题目很水吗?”
   “啊对不起不可以...”
   “那咱就无话可说了= =”
    话说连咱noip蒟蒻都觉得直接出搜索题也太囧了吧...虽然咱是一个连搜索剪枝都不会的大渣....
    做法:BFS...把16个格子看成二进制数,写两个进制相互转移的东西,直接扩展就可以了= =
=====================

program bzoj1054;
type arr=array[1..16]of longint;
var x:array[1..4]of longint=(-4,4,-1,1);
    y:array[1..16]of longint;
    z:array[1..16]of longint;
    hash:array[0..100000]of boolean;
    que,step:array[0..100000]of longint;
    er:array[0..16]of longint;
    ans:longint;

function calc(p:longint):arr;
var s:arr;
    i:longint;
begin
  for i:=1 to 16 do
   begin
     s[i]:=p and 1;
     p:=p shr 1;
   end;
  exit(s);
end;

function calc(p:arr):longint;
var s,i:longint;
begin
  s:=0;
  for i:=1 to 16 do
     s:=s+er[i]*p[i];
  exit(s);
end;

procedure bfs;
var l,r,stop,u,i,j,next:longint;
    now:arr;
begin
  fillchar(que,sizeof(que),0);
  fillchar(hash,sizeof(hash),false);
  l:=0;r:=1;
  que[l]:=calc(y);
  hash[que[l]]:=true;
  step[l]:=0;
  stop:=calc(z);
  while l<>r do
   begin
     u:=que[l];
     now:=calc(u);
     if u=stop then
      begin
       ans:=step[l];
       exit;
      end;
     for i:=1 to 16 do
      if now[i]=1 then
       for j:=1 to 4 do
        if (i+x[j]>0)and(i+x[j]<17)and(now[i+x[j]]=0)
        and(((i mod 4=1)and(x[j]<>-1))or((i mod 4=0)and(x[j]<>1))
        or((i mod 4<>1)and(i mod 4<>0))) then
         begin
           now[i+x[j]]:=1;
           now[i]:=0;
           next:=calc(now);
           if not hash[next] then
            begin
              hash[next]:=true;
              que[r]:=next;
              step[r]:=step[l]+1;
              inc(r);
              if next=stop then
               begin
                 ans:=step[r-1];
                 exit;
               end;
            end;
           now[i+x[j]]:=0;
           now[i]:=1;
         end;
     inc(l);
   end;
end;

procedure init;
var ch,s:string;
    i:longint;
begin
  s:='';
  for i:=1 to 4 do
   begin
     readln(ch);
     s:=s+ch;
   end;
  for i:=1 to 16 do
   y[i]:=ord(s[i])-ord('0');
  s:='';
  readln;
  for i:=1 to 4 do
   begin
     readln(ch);
     s:=s+ch;
   end;
  for i:=1 to 16 do
   z[i]:=ord(s[i])-ord('0');
  er[1]:=1;
  for i:=2 to 16 do
   er[i]:=er[i-1]*2;
  ans:=-1;
  bfs;
  write(ans);
end;

begin
  init;
end.


     
  评论这张
 
阅读(28)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017