加载中…
个人资料
sacredfantasy
sacredfantasy
  • 博客等级:
  • 博客积分:0
  • 博客访问:3,313
  • 关注人气:0
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

usaco 2.4.2 Overfencing

(2009-04-29 16:57:13)
标签:

usaco

2.4.2

overfencing

杂谈

分类: OI题解

usaco一贯的出题风格,比较繁琐,由于数组开小了,所以提交了7次!

Compiling...
Compile: OK

Executing...
   Test 1: TEST OK [0.011 secs, 1480 KB]
   Test 2: TEST OK [0.000 secs, 1480 KB]
   Test 3: TEST OK [0.000 secs, 1476 KB]
   Test 4: TEST OK [0.000 secs, 1480 KB]
   Test 5: TEST OK [0.011 secs, 1480 KB]
   Test 6: TEST OK [0.011 secs, 1480 KB]
   Test 7: TEST OK [0.000 secs, 1476 KB]
   Test 8: TEST OK [0.022 secs, 1480 KB]
   Test 9: TEST OK [0.000 secs, 1476 KB]
   Test 10: TEST OK [0.011 secs, 1480 KB]

All tests OK.

Your program ('maze1') produced all correct answers!  This is your
submission #7 for this problem.  Congratulations!

用dfs进行的话只可以过4个(如果不处理),以下是多进程bfs

program test;
type node=array[-1..500,-1..500]of longint;
var w,h,max,tail,head:longint;
 map:array[-1..500,-1..500]of char;
 dlx,dly:array[-1..10000]of integer;
 gt:node;
procedure main(a,b,a2,b2:longint;var g:node);//floodfill
var x,y:longint;
begin
 x:=0;y:=0;
 tail:=2;head:=0;
 dlx[1]:=a;
 dly[1]:=b;//出口1最先入队
 dlx[2]:=a2;
 dly[2]:=b2;//出口2再入队
 g[a div 2,b div 2]:=1;
 g[a2 div 2,b2 div 2]:=1;
 while head<=tail do
 begin
  inc(head);//头指针出队,读取新的节点.
  x:=dlx[head];
  y:=dly[head];
  //expand
  if (map[x+1,y]<>'-')and((x+2)<2*h+1)and(g[(x+2) div 2,y div 2]=0) then
  begin
   inc(tail);
   dlx[tail]:=x+2;
   dly[tail]:=y;
   g[(x+2) div 2,y div 2]:=g[x div 2,y div 2]+1;
  end;
  if (map[x-1,y]<>'-')and((x-2)>1)and(g[(x-2) div 2,y div 2]=0) then
  begin
   inc(tail);
   dlx[tail]:=x-2;
   dly[tail]:=y;
  g[(x-2) div 2,y div 2]:=g[x div 2,y div 2]+1;
  end;
  if (map[x,y+1]<>'|')and((y+2)<2*w+1)and(g[x div 2,(y+2) div 2]=0) then
  begin
   inc(tail);
   dlx[tail]:=x;
   dly[tail]:=y+2;
  g[x div 2,(y+2) div 2]:=g[x div 2,y div 2]+1;
  end;
  if (map[x,y-1]<>'|')and((y-2)>1)and(g[x div 2,(y-2) div 2]=0) then
  begin
   inc(tail);
   dlx[tail]:=x;
   dly[tail]:=y-2;
  g[x div 2,(y-2) div 2]:=g[x div 2,y div 2]+1;
  end;
 end;
end;
procedure init;
var i,j:integer;
begin
 readln(w,h);
 //初始化图
 for i:=1 to h*2+1 do
 begin
  for j:=1 to w*2+1 do
   read(map[i,j]);
  readln;
 end;
end;
procedure m1;
var i,j,s,a,b,a2,b2:integer;
begin
 //flood fill
 i:=0;s:=0;
 repeat
  if i=0 then i:=1 else i:=2*h+1;
  for j:=1 to w*2+1 do
  if map[i,j]=' ' then
  begin
   inc(s);
   case s of
   1:if (i=1) then begin a:=i+1;b:=j;end
   else begin a:=i-1;b:=j;end;
   2:if (i=1) then begin a2:=i+1;b2:=j;end
    else begin a2:=i-1;b2:=j;end;
   end;
  end;
 until i=2*h+1;
 j:=0;
 repeat
  if j=0 then j:=1 else j:=2*w+1;
  for i:=1 to h*2+1 do
  if map[i,j]=' ' then
  begin
   inc(s);
   case s of
   1:if j=1 then begin a:=i;b:=j+1;end
    else begin a:=i;b:=j-1;end;
   2:if j=1 then begin a2:=i;b2:=j+1;end
    else begin a2:=i;b2:=j-1;end;
   end;
  end;
 until j=2*w+1;
 fillchar(gt,sizeof(gt),0);
 main(a,b,a2,b2,gt);
 max:=0;
 for i:=1 to h do
  for j:=1 to w do
   if max<gt[i,j] then max:=gt[i,j];
 writeln(max);
end;
begin
  assign(input,'maze1.in');
  reset(input);
  assign(output,'maze1.out');
  rewrite(output);
  init;
  m1;
  close(input);
  close(output);
end.

0

阅读 评论 收藏 转载 喜欢 打印举报/Report
前一篇:usaco 2.4.1 ttwo
后一篇:kubuntu
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

    < 前一篇usaco 2.4.1 ttwo
    后一篇 >kubuntu
      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有