📄 usaco 2_4_1 the tamworth two 题解_leokan的blog.mht
字号:
href=3D"http://hi.baidu.com/leokan/profile">=B8=F6=C8=CB=B5=B5=B0=B8</A> =
<SPAN>|</SPAN><A=20
href=3D"http://hi.baidu.com/leokan/friends">=BA=C3=D3=D1</A> =
<SPAN>|</SPAN><A=20
href=3D"http://hi.baidu.com/leokan/modify/spbasic/0">=C9=E8=D6=C3</A> =
</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.1 The Tamworth Two =CC=E2=BD=E2</DIV>
<DIV class=3Ddate>2008=C4=EA01=D4=C230=C8=D5 =D0=C7=C6=DA=C8=FD =
15:56</DIV>
<TABLE style=3D"TABLE-LAYOUT: fixed">
<TBODY>
<TR>
<TD>
<DIV class=3Dcnt>
<H2>USACO 2.4.1 The Tamworth Two</H2>
<DIV class=3Dt_msgfont>The Tamworth Two<BR>BIO '98 - Richard =
Forster <BR>A=20
pair of cows is loose somewhere in the forest. Farmer John is =
lending his=20
expertise to their capture. Your task is to <SPAN class=3Dt_tag=20
href=3D"tag.php?name=3Dmod">mod</SPAN>el their behavior. =
<BR><BR>The chase=20
takes place on a 10 by 10 planar grid. Squares can be empty or =
they can=20
contain: <BR><BR>an obstacle, <BR>the cows (who always travel =
together),=20
or <BR>Farmer John. <BR>The cows and Farmer John can occupy the =
same=20
square (when they `meet') but neither the cows nor Farmer John can =
share a=20
square with an obstacle. Each square is<BR>represented<BR>as =
follows:=20
<BR><BR>. Empty square <BR>* Obstacle <BR>C Cows <BR>F Farmer =
<BR>Here is=20
a sample grid:=20
=
<BR>*...*.....<BR>......*...<BR>...*...*..<BR>..........<BR>...*.F....<BR=
>*.....*...<BR>...*......<BR>..C......*<BR>...*.*....<BR>.*.*......<BR><B=
R><BR><BR><BR>The=20
cows wander around the grid in a fixed way. Each minute, they =
either move=20
forward or rotate. Normally, they move one square in the direction =
they=20
are facing. If there is an obstacle in the way or they would leave =
the=20
board by walking `forward', then they spend the entire minute =
rotating 90=20
degrees clockwise. <BR><BR>Farmer John, wise in the ways of cows, =
moves in=20
exactly the same way. <BR><BR>The farmer and the cows can be =
considered to=20
move simultaneously during each minute. If the farmer and the cows =
pass=20
each other while moving, they are not considered to have met. The =
chase=20
ends when Farmer John and the cows occupy the same square at the =
end of a=20
minute. <BR><BR>Read a ten-line grid that represents the initial =
state of=20
the cows, Farmer John, and obstacles. Each of the ten lines =
contains=20
exactly ten characters using the coding above. There is guaranteed =
to be=20
only one farmer and one pair of cows. The cows and Farmer John =
will not=20
initially be on the same square. <BR><BR>Calculate the number of =
minutes=20
until the cows and Farmer John meet. Assume both the cows and =
farmer begin=20
the simulation facing in the `north' direction. Print 0 if they =
will never=20
meet. <BR><BR>PROGRAM NAME: ttwo<BR>INPUT FORMAT<BR>Lines=20
1-10: Ten lines of ten characters each, as explained =
above=20
<BR><BR>SAMPLE INPUT (file ttwo.in)=20
=
<BR>*...*.....<BR>......*...<BR>...*...*..<BR>..........<BR>...*.F....<BR=
>*.....*...<BR>...*......<BR>..C......*<BR>...*.*....<BR>.*.*......<BR><B=
R>OUTPUT=20
FORMAT<BR>A single line with the integer number of minutes until =
Farmer=20
John and the cows meet. Print 0 if they will never meet. =
<BR>SAMPLE OUTPUT=20
(file ttwo.out)<BR>49<BR><BR><BR><BR>The Tamworth=20
=
Two<BR><BR>=C1=BD=D6=BB=CB=FE=C4=B7=CE=D6=CB=B9=C5=A3<BR><BR>=D2=EB by =
Jure<BR>BOI '98? - Richard Forster=20
=
<BR><BR>=C1=BD=D6=BB=C5=A3=D4=DA=C9=AD=C1=D6=C0=EF=B9=CA=D2=E2=D7=DF=B6=AA=
=C1=CB=A1=A3=C5=A9=C3=F1John=BF=AA=CA=BC=D3=C3=CB=FB=B5=C4=D7=A8=BC=D2=BC=
=BC=CA=F5=D7=B7=B2=B6=D5=E2=C1=BD=CD=B7=C5=A3=A1=A3=C4=E3=B5=C4=C8=CE=CE=F1=
=CA=C7<SPAN class=3Dt_tag=20
=
href=3D"tag.php?name=3D%C4%A3%C4%E2">=C4=A3=C4=E2</SPAN>=CB=FB=C3=C7=B5=C4=
=D0=D0=CE=AA(=C5=A3=BA=CDJohn)=A1=A3=20
=
<BR><BR>=D7=B7=BB=F7=D4=DA10x10=B5=C4=C6=BD=C3=E6=CD=F8=B8=F1=C4=DA=BD=F8=
=D0=D0=A1=A3=D2=BB=B8=F6=B8=F1=D7=D3=BF=C9=D2=D4=CA=C7=A3=BA =
<BR><BR>=D2=BB=B8=F6=D5=CF=B0=AD=CE=EF, =
<BR>=C1=BD=CD=B7=C5=A3(=CB=FC=C3=C7=D7=DC=D4=DA=D2=BB=C6=F0), =
=BB=F2=D5=DF=20
<BR>=C5=A9=C3=F1John. =
<BR>=C1=BD=CD=B7=C5=A3=BA=CD=C5=A9=C3=F1John=BF=C9=D2=D4=D4=DA=CD=AC=D2=BB=
=B8=F6=B8=F1=D7=D3=C4=DA(=B5=B1=CB=FB=C3=C7=CF=E0=D3=F6=CA=B1)=A3=AC=B5=AB=
=CA=C7=CB=FB=C3=C7=B6=BC=B2=BB=C4=DC=BD=F8=C8=EB=D3=D0=D5=CF=B0=AD=B5=C4=B8=
=F1=D7=D3=A1=A3=20
<BR><BR>=D2=BB=B8=F6=B8=F1=D7=D3=BF=C9=D2=D4=CA=C7=A3=BA <BR><BR>. =
=BF=D5=B5=D8 <BR>* =D5=CF=B0=AD=CE=EF <BR>C =C1=BD=CD=B7=C5=A3 <BR>F =
=C5=A9=C3=F1John=20
<BR>=D5=E2=C0=EF=D3=D0=D2=BB=B8=F6=B5=D8=CD=BC=B5=C4=C0=FD=D7=D3:: =
=
<BR><BR>*...*.....<BR>......*...<BR>...*...*..<BR>..........<BR>...*.F...=
.<BR>*.....*...<BR>...*......<BR>..C......*<BR>...*.*....<BR>.*.*......<B=
R><BR><BR>=C5=A3=D4=DA=B5=D8=CD=BC=C0=EF=D2=D4=B9=CC=B6=A8=B5=C4=B7=BD=CA=
=BD=D3=CE=B5=B4=A1=A3=C3=BF=B7=D6=D6=D3=A3=AC=CB=FC=C3=C7=BF=C9=D2=D4=CF=F2=
=C7=B0=D2=C6=B6=AF=BB=F2=CA=C7=D7=AA=CD=E4=A1=A3=C8=E7=B9=FB=C7=B0=B7=BD=CE=
=DE=D5=CF=B0=AD=C7=D2=B2=BB=BB=E1=C0=EB=BF=AA=B5=D8=CD=BC=A3=AC=CB=FC=C3=C7=
=BB=E1=B0=B4=D5=D5=D4=AD=C0=B4=B5=C4=B7=BD=CF=F2=C7=B0=BD=F8=D2=BB=B2=BD=A1=
=A3=B7=F1=D4=F2=CB=FC=C3=C7=BB=E1=D3=C3=D5=E2=D2=BB=B7=D6=D6=D3=CB=B3=CA=B1=
=D5=EB=D7=AA90=B6=C8=A1=A3=20
<BR><BR>=C5=A9=C3=F1John, =
=C9=EE=D6=AA=C5=A3=B5=C4=D2=C6=B6=AF=B7=BD=B7=A8=A3=AC=CB=FB=D2=B2=D5=E2=C3=
=B4=D2=C6=B6=AF=A1=A3=20
=
<BR><BR>=C3=BF=B4=CE(=C3=BF=B7=D6=D6=D3)=C5=A9=C3=F1John=BA=CD=C1=BD=CD=B7=
=C5=A3=B5=C4=D2=C6=B6=AF=CA=C7=CD=AC=CA=B1=B5=C4=A1=A3=C8=E7=B9=FB=CB=FB=C3=
=C7=D4=DA=D2=C6=B6=AF=B5=C4=CA=B1=BA=F2=B4=A9=B9=FD=B6=D4=B7=BD=A3=AC=B5=AB=
=CA=C7=C3=BB=D3=D0=D4=DA=CD=AC=D2=BB=B8=F1=CF=E0=D3=F6=A3=AC=CE=D2=C3=C7=B2=
=BB=C8=CF=CE=AA=CB=FB=C3=C7=CF=E0=D3=F6=C1=CB=A1=A3=B5=B1=CB=FB=C3=C7=D4=DA=
=C4=B3=B7=D6=D6=D3=C4=A9=D4=DA=C4=B3=B8=F1=D7=D3=CF=E0=D3=F6=A3=AC=C4=C7=C3=
=B4=D7=B7=B2=B6=BD=E1=CA=F8=A1=A3=BF=AA=CA=BC=CA=B1=A3=ACJohn=BA=CD=C5=A3=
=B6=BC=C3=E6=CF=F2=B1=B1=B7=BD=A1=A3<BR><BR>PROGRAM=20
NAME: ttwo<BR>INPUT FORMAT<BR>Lines 1-10:=20
=
<BR>=C3=BF=D0=D010=B8=F6=D7=D6=B7=FB=A3=AC=B1=ED=CA=BE=C8=E7=C9=CF=CE=C4=C3=
=E8=CA=F6=B5=C4=B5=D8=CD=BC=A1=A3<BR><BR><BR>SAMPLE INPUT (file ttwo.in) =
=
<BR>*...*.....<BR>......*...<BR>...*...*..<BR>..........<BR>...*.F....<BR=
>*.....*...<BR>...*......<BR>..C......*<BR>...*.*....<BR>.*.*......<BR>OU=
TPUT=20
=
FORMAT<BR>=CA=E4=B3=F6=D2=BB=B8=F6=CA=FD=D7=D6=A3=AC=B1=ED=CA=BEJohn=D0=E8=
=D2=AA=B6=E0=C9=D9=CA=B1=BC=E4=B2=C5=C4=DC=D7=A5=D7=A1=C5=A3=C3=C7=A1=A3=CA=
=E4=B3=F60=A3=AC=C8=E7=B9=FBJohn=CE=DE=B7=A8=D7=A5=D7=A1=C5=A3=A1=A3<BR><=
BR>SAMPLE OUTPUT=20
(file ttwo.out)<BR>49</DIV>
<P></P>
<HR>
<P></P>
<P><STRONG>USACO 2.4.1 The Tamworth Two =
<BR>=CC=E1=BD=BB=B4=CE=CA=FD:2=B4=CE</STRONG></P>
=
<P><STRONG>=BF=B4=B4=ED=CC=E2=C1=CB,=C0=CB=B7=D1=C1=CB=D2=BB=B4=CE=CC=E1=BD=
=BB=BA=CD1=B8=F6=B6=E0=D6=D3=CD=B7=B5=C4=CA=B1=BC=E4,=D4=AD=C0=B4=D7=AA=D2=
=BB=CF=C2=D2=B2=CA=C7=D2=AA=BB=A8=D2=BB=B7=D6=D6=D3=B5=C4......=C6=E4=CA=B5=
=CE=D2=D4=E7=B8=C3=CF=EB=B5=BD=B5=C4,=B5=B1=CE=D2=C8=B7=B6=A8=CE=D2=CB=E3=
=B7=A8=CE=DE=B4=ED=B5=AB=CA=C7=CA=E4=B3=F6=B4=ED=CA=B1=CE=D2=BE=CD=D3=A6=B8=
=C3=CF=EB=B5=BD=CA=C7=CA=A1=B4=ED=CC=E2=C1=CB,=B5=AB=CA=C7=CE=D2=BB=B9=CA=
=C7=B8=FA=D7=D9=C1=CB=BA=DC=B6=E0=B1=E9=B2=C5=B7=A2=BE=F5=CA=A1=B4=ED=CC=E2=
.<BR>=D5=E2=B5=C0=CC=E2=C4=A3=C4=E2=BC=B4=BF=C9,=D3=C3=C5=A3=B5=C4=CE=BB=D6=
=C3=BA=CD=C5=A9=B7=F2=B5=C4=CE=BB=D6=C3=C5=D0=D6=D8,=D4=DA=D5=FD=B3=A3=D7=
=B4=BF=F6=CF=C2,=C3=BF=B6=D4=B5=E3=D7=EE=B6=E0=D4=DA=CD=AC=D2=BB=B8=F6=CE=
=BB=D6=C3=B3=F6=CF=D64=B4=CE,=BF=C9=D2=D4=BC=C7=C2=BC=B3=F6=CF=D6=B5=C4=B4=
=CE=CA=FD,=B4=F3=D3=DA3=B4=CE=D4=F2=CE=DE=BD=E2.</STRONG></P>
<P><STRONG>{<BR>TASK:ttwo<BR>LANG:PASCAL<BR>}<BR>program=20
ttwo;<BR>const<BR> turn:array[0..3,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..11,0..11] of boolean;<BR> =20
visit:array[1..10,1..10,1..10,1..10] of =
integer;<BR> =20
f,c:xy;<BR> fd,cd:integer;<BR>procedure=20
init;<BR>var<BR> =
i,j:integer;<BR> =20
ch:char;<BR>begin<BR> =20
assign(input,'ttwo.in');reset(input);<BR> =20
fillchar(map,sizeof(map),true);<BR> for i:=3D1 =
to 10=20
do<BR> =20
=
begin<BR> &nbs=
p;=20
for j:=3D1 to 10=20
=
do<BR> &=
nbsp; =20
=
begin<BR> &nbs=
p; =20
=
read(ch);<BR> =
=20
if ch=3D'*' then=20
=
map[i,j]:=3Dfalse;<BR> &nb=
sp; =20
if ch=3D'C' then begin=20
=
c[1]:=3Di;c[2]:=3Dj;end;<BR> &nb=
sp; =20
if ch=3D'F' then begin=20
=
f[1]:=3Di;f[2]:=3Dj;end;<BR> &nb=
sp; =20
=
end;<BR>  =
;=20
readln;<BR> =20
end;<BR> i:=3D0;for j:=3D0 to 11 do begin=20
map[i,j]:=3Dfalse;map[j,i]:=3Dfalse;end;<BR> =
i:=3D11;for j:=3D0=20
to 11 do begin =
map[i,j]:=3Dfalse;map[j,i]:=3Dfalse;end;<BR> =20
cd:=3D0;<BR> fd:=3D0;<BR> =20
fillchar(visit,sizeof(visit),false);<BR> =20
close(input);<BR>end;<BR>procedure=20
farmermove;<BR>begin<BR> if not=20
map[f[1]+turn[fd,1],f[2]+turn[fd,2]]=20
then<BR> =20
=
begin<BR> &nbs=
p;=20
=
inc(fd);<BR> &=
nbsp;=20
if fd=3D4 then =
fd:=3D0;<BR> =20
end<BR> else=20
=
begin<BR> &nbs=
p;=20
=
f[1]:=3Df[1]+turn[fd,1];<BR> &nb=
sp; =20
=
f[2]:=3Df[2]+turn[fd,2];<BR> =20
end;<BR>end;<BR>procedure cowmove;<BR>begin<BR> =
if not=20
map[c[1]+turn[cd,1],c[2]+turn[cd,2]]=20
then<BR> =20
=
begin<BR> &nbs=
p;=20
=
inc(cd);<BR> &=
nbsp;=20
if cd=3D4 then =
cd:=3D0;<BR> =20
end<BR> else=20
=
begin<BR> &nbs=
p;=20
=
c[1]:=3Dc[1]+turn[cd,1];<BR> &nb=
sp; =20
=
c[2]:=3Dc[2]+turn[cd,2];<BR> =20
end;<BR>end;</STRONG></P>
<P><STRONG>procedure work;<BR>var<BR> =20
step,time:integer;<BR>begin<BR> =20
assign(output,'ttwo.out');rewrite(output);<BR> =20
fillchar(visit,sizeof(visit),0);<BR> =20
step:=3D0;<BR> if not(map[f[1]+1,f[2]] or =
map[f[1]-1,f[2]]=20
or map[f[1],f[2]+1] or=20
=
map[f[1],f[2]-1])then<BR> =20
=
begin<BR> &nbs=
p;=20
=
writeln('0');<BR> &n=
bsp; =20
=
close(output);<BR> &=
nbsp; =20
exit;<BR> =20
end;<BR> if not(map[c[1]+1,c[2]] or =
map[c[1]-1,c[2]] or=20
map[c[1],c[2]+1] or=20
=
map[c[1],c[2]-1])then<BR> =20
=
begin<BR> &nbs=
p;=20
=
writeln('0');<BR> &n=
bsp; =20
=
close(output);<BR> &=
nbsp; =20
exit;<BR> =20
end;<BR> while =
visit[c[1],c[2],f[1],f[2]]<=3D4=20
do<BR> =20
=
begin<BR> &nbs=
p;=20
=
inc(visit[c[1],c[2],f[1],f[2]]);<BR> &=
nbsp; =20
=
farmermove;cowmove;<BR> &n=
bsp; =20
=
inc(step);<BR>  =
; =20
if (f[1]=3Dc[1])and(f[2]=3Dc[2])=20
=
then<BR>  =
; =20
=
begin<BR> &nbs=
p; =20
=
writeln(step);<BR> &=
nbsp; =20
=
close(output);<BR> &=
nbsp; =20
=
exit;<BR> &nbs=
p; =20
end;<BR> =20
end;<BR> writeln(0);<BR> =20
close(output);<BR>end;<BR>begin<BR> =20
init;<BR> work;<BR>end.<BR></STRONG></P><STRONG>
<HR>
</STRONG>
=
<P><STRONG>USACO=B5=C4=B7=D6=CE=F6,=CB=FC=CB=B5=D7=EE=B6=E0160000=B2=BD,=B1=
=ED=CA=BE=BB=B3=D2=C9...,=BF=C9=D2=D4=D3=C5=BB=AF=B5=C4</STRONG></P>
<P><STRONG>We can simply simulate the movement of Farmer John and =
the two=20
cows, but we need to find a way to detect loops. There are only =
100 places=20
where the cows can be, and 4 directions they can face. The same =
goes for=20
Farmer John. This multiplies out to 400*400 =3D 160,000 different =
(place,=20
direction) configurations for Farmer John and the cows. If we ever =
happen=20
upon a configuration we have been in before, we are in an infinite =
loop,=20
and John and the cows will never meet. </STRONG></P>
<P><STRONG>In fact, we don't even need to keep track of which=20
configurations we've seen. If they're going to meet, they're going =
to meet=20
in fewer than 160,000 steps. Otherwise, they have to repeat some=20
configuration, in which case they'll never meet. </STRONG></P>
<P><STRONG>We take care of the simulation by keeping track of the =
position=20
and direction of each. Direction is a number from 0 to 3, 0 =3D =
north, 1 =3D=20
east, 2 =3D south, 3 =3D west. So turning clockwise is =
incrementing one. We=20
calculate how to move given the direction by looking up offsets in =
the=20
deltax and deltay arrays. </STRONG></P><PRE><STRONG>/*
PROG: ttwo
ID: rsc001
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
char grid[10][10];
/* delta x, delta y position for moving north, east, south, west */
int deltax[] =3D { 0, 1, 0, -1 };
int deltay[] =3D { -1, 0, 1, 0 };
void
move(int *x, int *y, int *dir)
{
int nx, ny;
nx =3D *x+deltax[*dir];
ny =3D *y+deltay[*dir];
if(nx < 0 || nx >=3D 10 || ny < 0 || ny >=3D 10 || =
grid[ny][nx] =3D=3D '*')
*dir =3D (*dir + 1) % 4;
else {
*x =3D nx;
*y =3D ny;
}
}
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -