?? usaco 2_4_2 overfencing 題解_leokan的blog.mht
字號(hào):
</DIV></DIV>
<DIV class=3Dstage>
<DIV class=3Dstagepad>
<DIV style=3D"WIDTH: 100%">
<TABLE class=3Dmodth cellSpacing=3D0 cellPadding=3D0 width=3D"100%" =
border=3D0>
<TBODY>
<TR>
<TD class=3Dmodtl width=3D7> </TD>
<TD class=3Dmodtc noWrap>
<DIV class=3Dmodhead><SPAN =
class=3Dmodtit>=B2=E9=BF=B4=CE=C4=D5=C2</SPAN></DIV></TD>
<TD class=3Dmodtc noWrap align=3Dright>
<DIV class=3Dmodopt><A class=3Dmodact=20
href=3D"http://hi.baidu.com/leokan/creat/blog/"><IMG=20
src=3D"http://img.baidu.com/hi/img/ico_postnew.gif" =
align=3DabsMiddle=20
border=3D0>=D0=B4=D0=C2=CE=C4=D5=C2</A></DIV></TD>
<TD class=3Dmodtr width=3D7> </TD></TR></TBODY></TABLE>
<DIV class=3Dmodbox id=3Dm_blog>
<DIV class=3Dtit>USACO 2.4.2 Overfencing =CC=E2=BD=E2</DIV>
<DIV class=3Ddate>2008=C4=EA01=D4=C231=C8=D5 =D0=C7=C6=DA=CB=C4 =
09:46</DIV>
<TABLE style=3D"TABLE-LAYOUT: fixed">
<TBODY>
<TR>
<TD>
<DIV class=3Dcnt>
<CENTER><STRONG><FONT =
size=3D7>Overfencing</FONT></STRONG><BR>Kolstad and=20
Schrijvers </CENTER>
<P>Farmer John went crazy and created a huge maze of fences out in =
a=20
field. Happily, he left out two fence segments on the edges, and =
thus=20
created two "exits" for the maze. Even more happily, the maze he =
created=20
by this overfencing experience is a `perfect' maze: you can find a =
way out=20
of the maze from any point inside it.</P>
<P>Given W (1 <=3D W <=3D 38), the width of the maze; H (1 =
<=3D H <=3D=20
100), the height of the maze; 2*H+1 lines with width 2*W+1 =
characters that=20
represent the maze in a format like that shown later - then =
calculate the=20
number of steps required to exit the maze from the `worst' point =
in the=20
maze (the point that is `farther' from either exit even when =
walking=20
optimally to the closest exit). Of course, cows walk only parallel =
or=20
perpendicular to the x-y axes; they do not walk on a diagonal. =
Each move=20
to a new square counts as a single unit of distance (including the =
move=20
"out" of the maze.</P>
<P>Here's what one particular W=3D5, H=3D3 maze looks =
like:</P><PRE>+-+-+-+-+-+
| |
+-+ +-+ + +
| | | |
+ +-+-+ + +
| | | =20
+-+ +-+-+-+</PRE>
<P>Fenceposts appear only in odd numbered rows and and odd =
numbered=20
columns (as in the example). The format should be obvious and self =
explanatory. Each maze has exactly two blank walls on the outside =
for=20
exiting.</P>
<H3>PROGRAM NAME: maze1</H3>
<H3>INPUT FORMAT</H3>
<TABLE border=3D1>
<TBODY>
<TR>
<TD>Line 1:</TD>
<TD>W and H, space separated</TD></TR>
<TR>
<TD>Lines 2 through 2*H+2:</TD>
<TD>2*W+1 characters that represent the =
maze</TD></TR></TBODY></TABLE>
<H3>SAMPLE INPUT (file maze1.in)</H3><PRE>5 3
+-+-+-+-+-+
| |
+-+ +-+ + +
| | | |
+ +-+-+ + +
| | | =20
+-+ +-+-+-+</PRE>
<H3>OUTPUT FORMAT</H3>A single integer on a single output line. =
The=20
integer specifies the minimal number of steps that guarantee a cow =
can=20
exit the maze from any possible point inside the maze.=20
<H3>SAMPLE OUTPUT (file maze1.out)</H3>
<P>9</P>
<P>Overfencing<BR><BR>=B4=A9=D4=BD=D5=A4=C0=B8<BR>Kolstad and =
Schrijvers <BR><BR>=D2=EB by=20
=
lyl<BR><BR>=C5=A9=B7=F2John=D4=DA=CD=E2=C3=E6=B5=C4=CC=EF=D2=B0=C9=CF=B4=EE=
=BD=A8=C1=CB=D2=BB=B8=F6=BE=DE=B4=F3=B5=C4=D3=C3=D5=A4=C0=B8=CE=A7=B3=C9=B5=
=C4=C3=D4=B9=AC=A1=A3=D0=D2=D4=CB=B5=C4=CA=C7=A3=AC=CB=FB=D4=DA=C3=D4=B9=AC=
=B5=C4=B1=DF=BD=E7=C9=CF=C1=F4=B3=F6=C1=CB=C1=BD=B6=CE=D5=A4=C0=B8=D7=F7=CE=
=AA=C3=D4=B9=AC=B5=C4=B3=F6=BF=DA=A1=A3=B8=FC=D0=D2=D4=CB=B5=C4=CA=C7=A3=AC=
=CB=FB=CB=F9=BD=A8=D4=EC=B5=C4=C3=D4=B9=AC=CA=C7=D2=BB=B8=F6=A1=B0=CD=EA=C3=
=C0=B5=C4=A1=B1=C3=D4=B9=AC=A3=BA=BC=B4=C4=E3=C4=DC=B4=D3=C3=D4=B9=AC=D6=D0=
=B5=C4=C8=CE=D2=E2=D2=BB=B5=E3=D5=D2=B5=BD=D2=BB=CC=F5=D7=DF=B3=F6=C3=D4=B9=
=AC=B5=C4=C2=B7=A1=A3<BR>=B8=F8=B6=A8=C3=D4=B9=AC=B5=C4=BF=EDW(1<=3DW&=
lt;=3D38)=BC=B0=B3=A4H(1<=3DH<=3D100)=A1=A3<BR>2*H+1=D0=D0=A3=AC=C3=
=BF=D0=D02*W+1=B5=C4=D7=D6=B7=FB=D2=D4=CF=C2=C3=E6=B8=F8=B3=F6=B5=C4=B8=F1=
=CA=BD=B1=ED=CA=BE=D2=BB=B8=F6=C3=D4=B9=AC=A1=A3=C8=BB=BA=F3=BC=C6=CB=E3=B4=
=D3=C3=D4=B9=AC=D6=D0=D7=EE=A1=B0=D4=E3=B8=E2=A1=B1=B5=C4=C4=C7=D2=BB=B8=F6=
=B5=E3=D7=DF=B3=F6=C3=D4=B9=AC=CB=F9=D0=E8=B5=C4=B2=BD=CA=FD=A1=A3=A3=A8=BC=
=B4=CA=B9=B4=D3=D5=E2=D2=BB=B5=E3=D2=D4=D7=EE=D3=C5=B5=C4=B7=BD=CA=BD=D7=DF=
=CF=F2=D7=EE=BF=BF=BD=FC=B5=C4=B3=F6=BF=DA=A3=AC=CB=FC=C8=D4=C8=BB=D0=E8=D2=
=AA=D7=EE=B6=E0=B5=C4=B2=BD=CA=FD=A3=A9=B5=B1=C8=BB=C1=CB=A3=AC=C5=A3=C3=C7=
=D6=BB=BB=E1=CB=AE=C6=BD=BB=F2=B4=B9=D6=B1=B5=D8=D4=DAX=BB=F2Y=D6=E1=C9=CF=
=D2=C6=B6=AF=A3=AC=CB=FB=C3=C7=B4=D3=C0=B4=B2=BB=D7=DF=B6=D4=BD=C7=CF=DF=A1=
=A3=C3=BF=D2=C6=B6=AF=B5=BD=D2=BB=B8=F6=D0=C2=B5=C4=B7=BD=B8=F1=CB=E3=D7=F7=
=D2=BB=B2=BD=A3=A8=B0=FC=C0=A8=D2=C6=B3=F6=C3=D4=B9=AC=B5=C4=C4=C7=D2=BB=B2=
=BD=A3=A9<BR>=D5=E2=CA=C7=D2=BB=B8=F6W=3D5,H=3D3=B5=C4=C3=D4=B9=AC=A3=BA<=
/P><PRE>+-+-+-+-+-+
| |
+-+ +-+ + +
| | | |
+ +-+-+ + +
| | | =20
+-+ +-+-+-+</PRE>
=
<P>=C8=E7=C9=CF=CD=BC=B5=C4=C0=FD=D7=D3=A3=AC=D5=A4=C0=B8=B5=C4=D6=F9=D7=D3=
=D6=BB=B3=F6=CF=D6=D4=DA=C6=E6=CA=FD=D0=D0=BB=F2=C6=E6=CA=FD=C1=D0=A1=A3=C3=
=BF=B8=F6=C3=D4=B9=AC=D6=BB=D3=D0=C1=BD=B8=F6=B3=F6=BF=DA=A1=A3<BR>PROGRA=
M NAME: maze1</P>
<H3>PROGRAM NAME: maze1</H3>
<H3>INPUT FORMAT</H3>
<P>=B5=DA=D2=BB=D0=D0=A3=BA =
W=BA=CDH=A3=A8=D3=C3=BF=D5=B8=F1=B8=F4=BF=AA=A3=A9 =
<BR>=B5=DA=B6=FE=D0=D0=D6=C1=B5=DA2*H+2=D0=D0=A3=BA =
=C3=BF=D0=D02*W+1=B8=F6=D7=D6=B7=FB=B1=ED=CA=BE=C3=D4=B9=AC</P>
<H3>SAMPLE INPUT (file maze1.in)</H3><PRE>5 3
+-+-+-+-+-+
| |
+-+ +-+ + +
| | | |
+ +-+-+ + +
| | | =20
+-+ +-+-+-+</PRE>
<H3>OUTPUT FORMAT</H3>
=
<P>=CA=E4=B3=F6=D2=BB=B8=F6=B5=A5=B6=C0=B5=C4=D5=FB=CA=FD=A3=AC=B1=ED=CA=BE=
=C4=DC=B1=A3=D6=A4=C5=A3=B4=D3=C3=D4=B9=AC=D6=D0=C8=CE=D2=E2=D2=BB=B5=E3=D7=
=DF=B3=F6=C3=D4=B9=AC=B5=C4=D7=EE=D0=A1=B2=BD=CA=FD=A1=A3</P>
<H3>SAMPLE OUTPUT (file maze1.out)</H3>
<P>9</P>
<P></P>
<HR>
<P></P>
<P><STRONG>USACO 2.4.2 Overfencing =
<BR>=CC=E1=BD=BB=B4=CE=CA=FD:2=B4=CE</STRONG></P>
<P><STRONG>=D3=C3bfs=C0=B4flood=20
=
fill,=BD=AB=C8=EB=BF=DA=BC=D3=C8=EB=B6=D3=CA=D7,=D3=F6=B5=BD=C4=DC=D7=DF=C3=
=BB=D7=DF=B9=FD=B5=C4=B5=E3=D4=F2=BC=D3=C8=EB=B6=D3=CE=B2.=CE=D2=B6=D4=B6=
=D3=C1=D0=B5=C4=B3=A4=B6=C8=B9=C0=BC=C6=B5=C4=B2=BB=B9=BB...=D2=D4=BA=F3=D2=
=AA=C7=E5=B3=FE=B6=D3=C1=D0=B5=C4=D7=EE=B4=F3=B3=A4=B6=C8=B2=C5=BF=AA,=C3=
=BB=D3=D0=B0=D1=CE=D5=BE=CD=BF=AA=B4=F3=B5=E3,=CF=DE=B5=C3=CC=AB=CB=C0=C8=
=DD=D2=D7=B4=ED=CE=F3...</STRONG></P>
<P><STRONG>{<BR>TASK:maze1<BR>LANG:PASCAL<BR>}<BR>program=20
maze1;<BR>const<BR> next:array[1..4,1..2] of=20
=
integer=3D((-1,0),(0,1),(1,0),(0,-1));<BR>type<BR> =20
xy=3Darray[1..2] of integer;<BR>var<BR> =20
map:array[0..203,0..79] of boolean;<BR> =20
visit:array[0..203,0..79] of boolean;<BR> =20
queue:array[1..10000] of xy;<BR> =
count:array[1..10000]=20
of integer;<BR> n,m,h,t:integer;<BR>procedure=20
init;<BR>var<BR> =
i,j:integer;<BR> =20
ch:char;<BR>begin<BR> =20
assign(input,'maze1.in');reset(input);<BR> =20
readln(m,n);<BR> n:=3Dn shl 1 =
+1;<BR> =20
m:=3Dm shl 1 +1;<BR> =
h:=3D1;t:=3D0;<BR> =20
fillchar(map,sizeof(map),true);<BR> for i:=3D1 =
to n=20
do<BR> =20
=
begin<BR> &nbs=
p;=20
for j:=3D1 to m=20
=
do<BR> &=
nbsp; =20
=
begin<BR> &nbs=
p; =20
=
read(ch);<BR> =
=20
if (ch=3D'+')or(ch =3D'-')or(ch=3D'|')=20
=
then<BR>  =
; =
=20
=
map[i,j]:=3Dfalse<BR> &nbs=
p;  =
; =20
else if (i=3D1)or(i=3Dn)or(j=3D1)or(j=3Dm)=20
=
then<BR>  =
; =
=20
=
begin<BR> &nbs=
p;  =
; =20
=
inc(t);<BR> &n=
bsp; &nb=
sp; =20
=
queue[t,1]:=3Di;<BR>  =
; =
=20
=
queue[t,2]:=3Dj;<BR>  =
; =
=20
=
map[i,j]:=3Dfalse;<BR> &nb=
sp; &nbs=
p; =20
=
end;<BR>  =
; =20
=
end;<BR>  =
;=20
readln;<BR> =20
end;<BR> i:=3D0;for j:=3D0 to m+1 do=20
map[i,j]:=3Dfalse;<BR> i:=3Dn+1;for j:=3D0 to =
m+1 do=20
map[i,j]:=3Dfalse;<BR> j:=3D0;for i:=3D0 to n+1 =
do=20
map[i,j]:=3Dfalse;<BR> j:=3Dm+1;for i:=3D0 to =
n+1 do=20
map[i,j]:=3Dfalse;<BR> =20
fillchar(visit,sizeof(visit),false);<BR> =20
fillchar(count,sizeof(count),0);<BR> =20
close(input);<BR>end;<BR>procedure =
bfs;<BR>var<BR> =20
i:integer;<BR> temp:xy;<BR> =20
bo:boolean;<BR>begin<BR> while t>=3Dh=20
do<BR> =20
=
begin<BR> &nbs=
p;=20
for i:=3D1 to 4=20
=
do<BR> &=
nbsp; =20
=
begin<BR> &nbs=
p; =20
=
temp:=3Dqueue[h];<BR> &nbs=
p; =20
=
inc(temp[1],next[i,1]);<BR> &nbs=
p; =20
=
inc(temp[2],next[i,2]);<BR> &nbs=
p; =20
if map[temp[1],temp[2]] and not visit[temp[1],temp[2]]=20
=
then<BR>  =
; =
=20
=
begin<BR> &nbs=
p;  =
; =20
=
visit[temp[1],temp[2]]:=3Dtrue;<BR> &n=
bsp; &nb=
sp; =20
=
inc(t);<BR> &n=
bsp; &nb=
sp; =20
=
queue[t]:=3Dtemp;<BR> &nbs=
p;  =
; =20
=
count[t]:=3Dcount[h]+1;<BR> &nbs=
p;  =
; =20
=
end;<BR>  =
; =20
=
end;<BR>  =
;=20
inc(h);<BR> =20
end;<BR>end;<BR>procedure work;<BR>var<BR> =20
i,max,j:integer;<BR>begin<BR> =20
assign(output,'maze1.out');rewrite(output);<BR> =20
bfs;<BR> max:=3D0;<BR> for =
i:=3D1 to t=20
do<BR> if =
count[i]>max then=20
max:=3Dcount[i];<BR> writeln((max+1)shr=20
1);<BR> =20
close(output);<BR>end;<BR>begin<BR> =20
init;<BR> work;<BR>end.</STRONG></P><STRONG>
<HR>
</STRONG>
<P><STRONG>USACO=B5=C4=B7=D6=CE=F6,=B4=F3=B8=C5=D2=B2=CA=C7flood =
fill</STRONG></P>
<P><STRONG>We can solve this with a standard flood fill, using a =
queue to=20
implement breadth first search. It is convenient to leave the maze =
in its=20
ASCII format and just look at it as a bunch of characters, with =
non-space=20
characters being walls. </STRONG></P><PRE><STRONG>#include =
<stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#define MAXWID 38
#define MAXHT 100
typedef struct Point Point;
struct Point {
int r, c;
};
int wid, ht;
char maze[MAXHT*2+1][MAXWID*2+1+2]; /* extra +2 for "\n\0" */
int dist[MAXHT*2+1][MAXWID*2+1];
Point
Pt(int r, int c)
{
Point p;
p.r =3D r;
p.c =3D c;
return p;
}
typedef struct Queue Queue;
struct Queue {
Point p;
int d;
};
Queue floodq[MAXHT*MAXWID];
int bq, eq;
/* if no wall between point p and point np, add np to queue with =
distance d+1 */
void
addqueue(int d, Point p, Point np)
{
if(maze[(p.r+np.r)/2][(p.c+np.c)/2] =3D=3D ' ' && =
maze[np.r][np.c] =3D=3D ' ') {
maze[np.r][np.c] =3D '*';
floodq[eq].p =3D np;
floodq[eq].d =3D d+1;
eq++;
}
}
/* if there is an exit at point exitp, plug it and record a start point
* at startp */
void
lookexit(Point exitp, Point startp)
{
if(maze[exitp.r][exitp.c] =3D=3D ' ') {
addqueue(0, startp, startp);
maze[exitp.r][exitp.c] =3D '#';
}
}
void
main(void)
{
FILE *fin, *fout;
Point p;
int i, r, c, m, d;
fin =3D fopen("maze1.in", "r");
fout =3D fopen("maze1.out", "w");
assert(fin !=3D NULL && fout !=3D NULL);
fscanf(fin, "%d %d\n", &wid, &ht);
wid =3D 2*wid+1;
ht =3D 2*ht+1;
for(i=3D0; i<ht; i++)
fgets(maze[i], sizeof(maze[i]), fin);
/* find exits */
for(i=3D1; i<wid; i+=3D2) {
lookexit(Pt(0, i), Pt(1, i));
lookexit(Pt(ht-1, i), Pt(ht-2, i));
?? 快捷鍵說(shuō)明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號(hào)
Ctrl + =
減小字號(hào)
Ctrl + -