📄 usaco 1_2_2 transformations 题解_leokan的blog.mht
字号:
<DIV id=3Dtabline></DIV>
<DIV id=3Dtab><A href=3D"http://hi.baidu.com/leokan">=D6=F7=D2=B3</A><A =
class=3Don=20
href=3D"http://hi.baidu.com/leokan/blog">=B2=A9=BF=CD</A><A=20
href=3D"http://hi.baidu.com/leokan/album">=CF=E0=B2=E1</A><SPAN>|</SPAN><=
A=20
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> =
</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></TD>
<TD class=3Dmodtr width=3D7> </TD></TR></TBODY></TABLE>
<DIV class=3Dmodbox id=3Dm_blog>
<DIV class=3Dtit>USACO 1.2.2 Transformations =CC=E2=BD=E2</DIV>
<DIV class=3Ddate>2007=C4=EA12=D4=C230=C8=D5 =D0=C7=C6=DA=C8=D5 =
20:13</DIV>
<TABLE style=3D"TABLE-LAYOUT: fixed">
<TBODY>
<TR>
<TD>
<DIV class=3Dcnt>
<H2>USACO 1.2.2 Transformations</H2>
<P class=3Dt_msgfont>Transformations<BR><BR>A square pattern of =
size N x N=20
(1 <=3D N <=3D 10) black and white square tiles is =
transformed into=20
another square pattern. Write a program that will recognize the =
minimum=20
transformation that has been applied to the original pattern given =
the=20
following <SPAN class=3Dt_tag =
href=3D"tag.php?name=3Dlis">lis</SPAN>t of=20
possible transformations: <BR><BR>#1: 90 Degree Rotation: The =
pattern was=20
rotated clockwise 90 degrees. <BR>#2: 180 Degree Rotation: The =
pattern was=20
rotated clockwise 180 degrees. <BR>#3: 270 Degree Rotation: The =
pattern=20
was rotated clockwise 270 degrees. <BR>#4: Reflection: The pattern =
was=20
reflected horizontally (turned into a mirror image of itself by =
reflecting=20
around a vertical line in the middle of the image). <BR>#5: =
Combination:=20
The pattern was reflected horizontally and then subjected to one =
of the=20
rotations (#1-#3). <BR>#6: No Change: The original pattern was not =
changed. <BR>#7: Invalid Transformation: The new pattern was not =
obtained=20
by any of the above methods. <BR>In the case that more than one =
transform=20
could have been used, choose the one with the minimum number =
above.=20
<BR><BR>PROGRAM NAME: transform<BR>INPUT FORMAT<BR>Line =
1: A=20
single integer, N <BR>Line 2..N+1: N lines =
of N=20
characters (each either `@' or `-'); this is the square before=20
transformation <BR>Line N+2..2*N+1: N lines of N =
characters=20
(each either `@' or `-'); this is the square after transformation=20
<BR><BR>SAMPLE INPUT (file transform.in)=20
<BR>3<BR>@-@<BR>---<BR>@@-<BR>@-@<BR>@--<BR>--@<BR><BR>OUTPUT =
FORMAT<BR>A=20
single line containing the the number from 1 through 7 (described =
above)=20
that categorizes the transformation required to change from the =
`before'=20
representation to the `after' representation. <BR>SAMPLE OUTPUT =
(file=20
=
transform.out)<BR>1<BR><BR><BR><BR>Transformations<BR><BR>=B7=BD=BF=E9=D7=
=AA=BB=BB<BR><BR>=D2=EB=20
by TinyTony<BR><BR>=D2=BB=BF=E9N x=20
=
N=A3=A81<=3DN<=3D10=A3=A9=D5=FD=B7=BD=D0=CE=B5=C4=BA=DA=B0=D7=CD=DF=
=C6=AC=B5=C4=CD=BC=B0=B8=D2=AA=B1=BB=D7=AA=BB=BB=B3=C9=D0=C2=B5=C4=D5=FD=B7=
=BD=D0=CE=CD=BC=B0=B8=A1=A3=D0=B4=D2=BB=B8=F6=B3=CC=D0=F2=C0=B4=D5=D2=B3=F6=
=BD=AB=D4=AD=CA=BC<BR>=CD=BC=B0=B8=B0=B4=D5=D5=D2=D4=CF=C2=C1=D0=D7=AA=BB=
=BB=B7=BD=B7=A8=D7=AA=BB=BB=B3=C9=D0=C2=CD=BC=B0=B8=B5=C4=D7=EE=D0=A1=B7=BD=
=CA=BD=A3=BA<BR>#1=A3=BA=D7=AA90=B6=C8=A3=BA=CD=BC=B0=B8=B0=B4=CB=B3=CA=B1=
=D5=EB=D7=AA90=B6=C8=A1=A3<BR>#2=A3=BA=D7=AA180=B6=C8=A3=BA=CD=BC=B0=B8=B0=
=B4=CB=B3=CA=B1=D5=EB=D7=AA180=B6=C8=A1=A3<BR>#3=A3=BA=D7=AA270=B6=C8=A3=BA=
=CD=BC=B0=B8=B0=B4=CB=B3=CA=B1=D5=EB=D7=AA270=B6=C8=A1=A3<BR>#4=A3=BA=B7=B4=
=C9=E4=A3=BA=CD=BC=B0=B8=D4=DA=CB=AE=C6=BD=B7=BD=CF=F2=B7=AD=D7=AA=A3=A8=D0=
=CE=B3=C9=D4=AD=CD=BC=B0=B8=B5=C4=BE=B5=CF=F1=A3=A9=A1=A3<BR>#5=A3=BA=D7=E9=
=BA=CF=A3=BA=CD=BC=B0=B8=D4=DA=CB=AE=C6=BD=B7=BD=CF=F2=B7=AD=D7=AA=A3=AC=C8=
=BB=BA=F3=B0=B4=D5=D5#1-#3=D6=AE=D2=BB=D7=AA=BB=BB=A1=A3<BR>#6=A3=BA=B2=BB=
=B8=C4=B1=E4=A3=BA=D4=AD=CD=BC=B0=B8=B2=BB=B8=C4=B1=E4=A1=A3<BR>#7=A3=BA=CE=
=DE=D0=A7=D7=AA=BB=BB=A3=BA=CE=DE=B7=A8=D3=C3=D2=D4=C9=CF=B7=BD=B7=A8=B5=C3=
=B5=BD=D0=C2=CD=BC=B0=B8=A1=A3<BR>=C8=E7=B9=FB=D3=D0=B6=E0=D6=D6=BF=C9=D3=
=C3=B5=C4=D7=AA=BB=BB=B7=BD=B7=A8=A3=AC=C7=EB=D1=A1=D4=F1=D0=F2=BA=C5=D7=EE=
=D0=A1=B5=C4=C4=C7=B8=F6=A1=A3<BR><BR>PROGRAM=20
NAME: transform<BR>INPUT FORMAT<BR>=B5=DA=D2=BB=D0=D0=A3=BA =
=B5=A5=B6=C0=B5=C4=D2=BB=B8=F6=D5=FB=CA=FDN=A1=A3 =
<BR>=B5=DA=B6=FE=D0=D0=B5=BD=B5=DAN+1=D0=D0=A3=BA=20
=
N=D0=D0=C3=BF=D0=D0N=B8=F6=D7=D6=B7=FB=A3=A8=B2=BB=CA=C7=A1=B0@=A1=B1=BE=CD=
=CA=C7=A1=B0-=A1=B1=A3=A9=A3=BB=D5=E2=CA=C7=D7=AA=BB=BB=C7=B0=B5=C4=D5=FD=
=B7=BD=D0=CE=A1=A3 <BR>=B5=DAN+2=D0=D0=B5=BD=B5=DA2*N+1=D0=D0=A3=BA=20
=
N=D0=D0=C3=BF=D0=D0N=B8=F6=D7=D6=B7=FB=A3=A8=B2=BB=CA=C7=A1=B0@=A1=B1=BE=CD=
=CA=C7=A1=B0-=A1=B1=A3=A9=A3=BB=D5=E2=CA=C7=D7=AA=BB=BB=BA=F3=B5=C4=D5=FD=
=B7=BD=D0=CE=A1=A3 <BR><BR>SAMPLE INPUT (file=20
=
transform.in)<BR>3<BR>@-@<BR>---<BR>@@-<BR>@-@<BR>@--<BR>--@<BR><BR>OUTPU=
T=20
=
FORMAT<BR><BR>=B5=A5=B6=C0=B5=C4=D2=BB=D0=D0=B0=FC=C0=A81=B5=BD7=D6=AE=BC=
=E4=B5=C4=D2=BB=B8=F6<SPAN class=3Dt_tag=20
=
href=3D"tag.php?name=3D%CA%FD%D7%D6">=CA=FD=D7=D6</SPAN>=A3=A8=D4=DA=C9=CF=
=CE=C4=D2=D1=C3=E8=CA=F6=A3=A9=B1=ED=C3=F7=D0=E8=D2=AA=BD=AB=D7=AA=BB=BB=C7=
=B0=B5=C4=D5=FD=B7=BD=D0=CE=B1=E4=CE=AA=D7=AA=BB=BB=BA=F3=B5=C4=D5=FD=B7=BD=
=D0=CE=B5=C4<BR>=D7=AA=BB=BB=B7=BD=B7=A8=A1=A3<BR><BR>SAMPLE=20
OUTPUT (file transform.out)<BR><BR>1</P>
<DIV class=3Dt_msgfont><STRONG>TASK: transform<BR>LANG:=20
PASCAL</STRONG></DIV>
<P></P>
<P><STRONG>Compiling...<BR>Compile: OK</STRONG></P>
<P><STRONG>Executing...<BR> Test 1: =
TEST OK=20
[0 secs]<BR> Test 2: TEST OK [0.004=20
secs]<BR> Test 3: TEST OK [0=20
secs]<BR> Test 4: TEST OK [0.004=20
secs]<BR> Test 5: TEST OK [0=20
secs]<BR> Test 6: TEST OK [0.004=20
secs]<BR> Test 7: TEST OK [0=20
secs]<BR> Test 8: TEST OK [0=20
secs]</STRONG></P>
<P><STRONG>All tests OK.<BR>YOUR PROGRAM ('transform') WORKED =
FIRST TIME!=20
That's fantastic<BR>-- and a rare thing. Please accept these =
special=20
automated<BR>congratulations.</STRONG></P>
=
<P><STRONG>=D5=E2=CC=E2=BF=B4=CB=C6=B8=B4=D4=D3=A3=AC=C6=E4=CA=B5=D2=BB=B9=
=B2=D6=BB=D3=D02=D6=D6=D7=AA=BB=BB=B7=BD=CA=BD=A3=AC=BC=B4=D0=FD=D7=AA90=B6=
=C8=BA=CD=D7=F3=D3=D2=B7=AD=D7=AA=A3=AC=B6=BC=CA=C7=BA=DC=BC=F2=B5=A5=B5=C4=
=B9=FD=B3=CC=A3=AC=C8=BB=BA=F3=B0=B4=D2=AA=C7=F3=C4=A3=C4=E2=BC=B4=BF=C9=A1=
=A3=D2=BB=B4=CEAC=A3=A1</STRONG></P>
=
<P><STRONG>=D7=EE=BD=FC=D3=D0=C8=CB=D2=AA=C7=F3=CE=D2=CC=F9=B3=CC=D0=F2=A3=
=AC=CE=D2=B1=BE=C0=B4=CA=C7=B2=BB=D6=A7=B3=D6=B5=C4=A3=AC=D7=F6=CC=E2=BF=B4=
=CC=E2=BD=E2=D2=D1=BE=AD=CA=C7=CD=F2=B2=BB=B5=C3=D2=D1=A3=AC=BF=B4=B3=CC=D0=
=F2=BE=CD=C3=BB=CA=B2=C3=B4=D2=E2=CB=BC=C1=CB=A3=AC=B5=AB=CA=C7=CE=D2=BB=B9=
=CA=C7=B0=D1=B3=CC=D0=F2=CC=F9=B3=F6=C0=B4=B0=C9=A1=A3</STRONG></P>
<P><STRONG>code=A3=BA</STRONG></P>
<P><STRONG>{<BR>TASK:transform<BR>LANG:PASCAL<BR>}<BR>program=20
transform;<BR>type<BR> arr=3Darray[1..10,1..10] =
of=20
1..2;<BR>var<BR> =20
start,temp,final:arr;<BR> =
n:integer;</STRONG></P>
<P><STRONG>procedure =
outt(x:integer);<BR>begin<BR> =20
=
assign(output,'transform.out');rewrite(output);<BR> =20
writeln(x);<BR> halt;<BR> =20
close(output);<BR>end;<BR>procedure =
init;<BR>var<BR> =20
i,j:integer;<BR> =
ch:char;<BR>begin<BR> =20
assign(input,'transform.in');reset(input);<BR> =20
readln(n);<BR> for i:=3D1 to n=20
do<BR> =20
begin<BR> for j:=3D1 to =
n=20
=
do<BR> =
=
begin<BR> &nbs=
p;=20
=
read(ch);<BR> =
=20
if <A href=3D"mailto:ch=3D%20@">mailto:ch=3D%20@</A> then =
start[i,j]:=3D1 else=20
=
start[i,j]:=3D2;<BR>  =
; =20
end;<BR> =20
readln;<BR> =20
end;<BR> for i:=3D1 to n=20
do<BR> =20
begin<BR> for j:=3D1 to =
n=20
=
do<BR> =
=
begin<BR> &nbs=
p;=20
=
read(ch);<BR> =
=20
if <A href=3D"mailto:ch=3D%20@">mailto:ch=3D%20@</A> then =
final[i,j]:=3D1 else=20
=
final[i,j]:=3D2;<BR>  =
; =20
end;<BR> =20
readln;<BR> =20
end;<BR> close(input);<BR>end;<BR>function=20
check(b:arr):boolean;<BR>var<BR> =20
i,j:integer;<BR>begin<BR> =20
check:=3Dtrue;<BR> for i:=3D1 to n =
do<BR> =20
for j:=3D1 to n do<BR> =
if=20
b[i,j]<>final[i,j]=20
=
then<BR>  =
;=20
=
begin<BR> &nbs=
p;=20
=
check:=3Dfalse;<BR> =
=20
=
exit;<BR> &nbs=
p;=20
end;<BR>end;</STRONG></P>
<P><STRONG>procedure s90(var b:arr);<BR>var<BR> =20
i,j:integer;<BR> =
t:arr;<BR>begin<BR> =20
t:=3Db;<BR> for i:=3D1 to n =
do<BR> for=20
j:=3D1 to n do<BR> =20
b[j,n-i+1]:=3Dt[i,j];<BR>end;<BR>procedure fs(var=20
b:arr);<BR>var<BR> =
i,j:integer;<BR> =20
t:arr;<BR>begin<BR> =
t:=3Db;<BR> for i:=3D1=20
to n do<BR> for j:=3D1 to n =
do<BR> =20
b[i,j]:=3Dt[i,n-j+1];<BR>end;<BR>procedure=20
main;<BR>var<BR> =20
step:integer;<BR>begin<BR> =20
step:=3D1;<BR> =
temp:=3Dstart;<BR> =20
s90(temp);<BR> if check(temp) then=20
outt(step);<BR> inc(step);<BR> =
s90(temp);<BR> if check(temp) then=20
outt(step);<BR> inc(step);<BR> =
s90(temp);<BR> if check(temp) then=20
outt(step);<BR> inc(step);<BR> =
temp:=3Dstart;<BR> =
fs(temp);<BR> if=20
check(temp) then outt(step);<BR> =20
inc(step);<BR> s90(temp);<BR> =
if=20
check(temp) then outt(step);<BR> =20
s90(temp);<BR> if check(temp) then=20
outt(step);<BR> s90(temp);<BR> =
if=20
check(temp) then outt(step);<BR> =20
inc(step);<BR> if check(start) then=20
outt(step);<BR> =20
=
inc(step);outt(step);<BR>end;<BR>begin<BR>init;<BR>main;<BR>end.</STRONG>=
</P>
=
<P><STRONG>=CF=C2=C3=E6=CA=C7USACO=B5=C4=B7=D6=CE=F6=A3=A8Analysis){c=D3=EF=
=D1=D4}</STRONG></P>
<P><STRONG>Transformations<BR>Russ Cox <BR>We represent a board as =
a data=20
structure containing the dimension and the contents. We pass =
around the=20
data structure itself, not a reference to it, so that we can =
return new=20
boards, and so on. </STRONG></P>
<P><STRONG>This makes it easy to define reflect and rotate =
operations that=20
return reflected and rotated boards. </STRONG></P>
<P><STRONG>Once we have these, we just check to see what =
combination of=20
transformations makes the old board into the new board. =
</STRONG></P>
<P><STRONG>#include <stdio.h><BR>#include=20
<stdlib.h><BR>#include <string.h><BR>#include=20
<assert.h></STRONG></P>
<P><STRONG>#define MAXN 10</STRONG></P>
<P><STRONG>typedef struct Board Board;<BR>struct Board=20
{<BR> int n;<BR> char=20
b[MAXN][MAXN];<BR>};</STRONG></P>
<P><STRONG>/* rotate 90 degree clockwise: [r, c] -> [c, n+1 - =
r]=20
*/<BR>Board<BR>rotate(Board b)<BR>{<BR> Board=20
nb;<BR> int r, c;</STRONG></P>
<P><STRONG> nb =3D b;<BR> =
for(r=3D0;=20
r<b.n; r++)<BR> for(c=3D0; c<b.n;=20
c++)<BR> nb.b[c][b.n+1 - =
r] =3D=20
b.b[r][c];</STRONG></P>
<P><STRONG> return nb;<BR>}</STRONG></P>
<P><STRONG>/* reflect board horizontally: [r, c] -> [r, n-1 -c] =
*/<BR>Board<BR>reflect(Board b)<BR>{<BR> Board=20
nb;<BR> int r, c;</STRONG></P>
<P><STRONG> nb =3D b;<BR> =
for(r=3D0;=20
r<b.n; r++)<BR> for(c=3D0; c<b.n;=20
c++)<BR> nb.b[r][b.n-1 - =
c] =3D=20
b.b[r][c];</STRONG></P>
<P><STRONG> return nb;<BR>}</STRONG></P>
<P><STRONG>/* return non-zero if and only if boards are equal=20
*/<BR>int<BR>eqboard(Board b, Board bb)<BR>{<BR> =
int r,=20
c;</STRONG></P>
<P><STRONG> if(b.n !=3D=20
bb.n)<BR> return =
0;</STRONG></P>
<P><STRONG> for(r=3D0; r<b.n;=20
r++)<BR> for(c=3D0; c<b.n;=20
c++)<BR> if(b.b[r][c] =
!=3D=20
=
bb.b[r][c])<BR> &nbs=
p; =20
return 0;<BR> return 1;<BR>}</STRONG></P>
<P><STRONG>Board<BR>rdboard(FILE *fin, int =
n)<BR>{<BR> =20
Board b;<BR> int r, c;</STRONG></P>
<P><STRONG> b.n =3D n;<BR> =
for(r=3D0;=20
r<n; r++) {<BR> =
for(c=3D0;=20
c<n;=20
=
c++)<BR>  =
;=20
b.b[r][c] =3D =
getc(fin);<BR> =20
assert(getc(fin) =3D=3D '\n');<BR> =
}<BR> =20
return b;<BR>}</STRONG></P>
<P><STRONG>void<BR>main(void)<BR>{<BR> FILE =
*fin,=20
*fout;<BR> Board b, nb;<BR> =
int n,=20
change;</STRONG></P>
<P><STRONG> fin =3D fopen("transform.in",=20
"r");<BR> fout =3D fopen("transform.out",=20
"w");<BR> assert(fin !=3D NULL && fout =
!=3D=20
NULL);</STRONG></P>
<P><STRONG> fscanf(fin, "%d\n",=20
&n);<BR> b =3D rdboard(fin, =
n);<BR> =20
nb =3D rdboard(fin, n);</STRONG></P>
<P><STRONG> if(eqboard(nb,=20
rotate(b)))<BR> change =
=3D=20
1;<BR> else if(eqboard(nb,=20
rotate(rotate(b))))<BR> =
change =3D=20
2;<BR> else if(eqboard(nb,=20
=
rotate(rotate(rotate(b)))))<BR> =
=20
change =3D 3;<BR> else if(eqboard(nb,=20
reflect(b)))<BR> change =
=3D=20
4;<BR> else if(eqboard(nb,=20
=
rotate(reflect(b)))<BR> =
||=20
eqboard(nb,=20
=
rotate(rotate(reflect(b))))<BR> =
=20
|| eqboard(nb,=20
=
rotate(rotate(rotate(reflect(b))))))<BR> &nb=
sp; =20
change =3D 5;<BR> else if(eqboard(nb,=20
b))<BR> change =3D=20
6;<BR> =20
else<BR> change =3D=20
7;</STRONG></P>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -