📄 usaco 3_3_4 home on the range 题解_leokan的blog.mht
字号:
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 3.3.4 Home on the Range =CC=E2=BD=E2</DIV>
<DIV class=3Ddate>2008=C4=EA02=D4=C209=C8=D5 =D0=C7=C6=DA=C1=F9 =
21:05</DIV>
<TABLE style=3D"TABLE-LAYOUT: fixed">
<TBODY>
<TR>
<TD>
<DIV class=3Dcnt>
<H2>USACO 3.3.4 Home on the Range</H2>
<DIV class=3Dt_msgfont>Home on the Range<BR><BR>Farmer John grazes =
his cows=20
on a large, square field N (2 <=3D N <=3D 250) miles on a =
side (because,=20
for some reason, his cows will only graze on precisely square land =
segments). Regrettably, the cows have ravaged some of the land =
(always in=20
1 mile square increments). FJ needs to map the remaining squares =
(at least=20
2x2 on a side) on which his cows can graze (in these larger =
squares, no=20
1x1 mile segments are ravaged). <BR><BR>Your task is to count up =
all the=20
various square grazing areas within the supplied dataset and =
report the=20
number of square grazing areas (of sizes >=3D 2x2) remaining. =
Of course,=20
grazing areas may overlap for purposes of this report. =
<BR><BR>PROGRAM=20
NAME: range<BR>INPUT FORMAT<BR>Line 1: N, the number =
of miles=20
on each side of the field. <BR>Line 2..N+1: N =
characters with=20
no spaces. 0 represents "ravaged for that block; 1 represents =
"ready to=20
eat". <BR><BR>SAMPLE INPUT (file range.in)=20
=
<BR>6<BR>101111<BR>001111<BR>111111<BR>001111<BR>101101<BR>111001<BR><BR>=
OUTPUT=20
FORMAT<BR>Potentially several lines with the size of the square =
and the=20
number of such squares that exist. Order them in ascending order =
from=20
smallest to largest size. <BR><BR>SAMPLE OUTPUT (file =
range.out)<BR>2=20
10<BR>3 4<BR>4 1 <BR><BR><BR><BR>Home on the Range=20
<BR><BR>=BC=D2=B5=C4=B7=B6=CE=A7<BR><BR>=D2=EB by tim =
green<BR><BR><BR>=C5=A9=C3=F1=D4=BC=BA=B2=D4=DA=D2=BB=C6=AC=B1=DF=B3=A4=CA=
=C7N (2 <=3D N <=3D=20
=
250)=D3=A2=C0=EF=B5=C4=D5=FD=B7=BD=D0=CE=C4=C1=B3=A1=C9=CF=B7=C5=C4=C1=CB=
=FB=B5=C4=C4=CC=C5=A3=A1=A3<BR>(=D2=F2=CE=AA=D2=BB=D0=A9=D4=AD=D2=F2=A3=AC=
=CB=FB=B5=C4=C4=CC=C5=A3=D6=BB=D4=DA=D5=FD=B7=BD=D0=CE=B5=C4=C4=C1=B3=A1=C9=
=CF=B3=D4=B2=DD=A1=A3)<BR>=D2=C5=BA=B6=B5=C4=CA=C7,=CB=FB=B5=C4=C4=CC=C5=A3=
=D2=D1=BE=AD=BB=D9=BB=B5=D2=BB=D0=A9=CD=C1=B5=D8=A1=A3(=20
=
=D2=BB=D0=A91=C6=BD=B7=BD=D3=A2=C0=EF=B5=C4=D5=FD=B7=BD=D0=CE)<BR>=C5=A9=C3=
=F1=D4=BC=BA=B2=D0=E8=D2=AA=CD=B3=BC=C6=C4=C7=D0=A9=BF=C9=D2=D4=B7=C5=C4=C1=
=C4=CC=C5=A3=B5=C4=D5=FD=B7=BD=D0=CE=C4=C1=B3=A1(=D6=C1=C9=D9=CA=C72x2=B5=
=C4,=D4=DA=D5=E2=D0=A9=BD=CF=B4=F3=B5=C4=D5=FD=B7=BD=D0=CE=D6=D0=C3=BB=D3=
=D0=D0=A1=D3=DA1x1=B5=C4=B2=BF=B7=D6=B1=BB=B7=D6=B8=EE=BB=D9=BB=B5)=A1=A3=
<BR>=C4=E3=B5=C4=B9=A4=D7=F7=D2=AA=D4=DA=B1=BB=B9=A9=D3=A6=B5=C4<SPAN=20
class=3Dt_tag=20
=
href=3D"tag.php?name=3D%CA%FD%BE%DD">=CA=FD=BE=DD</SPAN>=D7=E9=C0=EF=C3=E6=
=CD=B3=BC=C6=CB=F9=D3=D0=B2=BB=CD=AC=B5=C4=D5=FD=B7=BD=D0=CE=B7=C5=C4=C1=C7=
=F8=D3=F2(>2x2)=B5=C4=B8=F6=CA=FD=A1=A3<BR>=B5=B1=C8=BB=A3=AC=B7=C5=C4=
=C1=C7=F8=D3=F2=BF=C9=C4=DC=CA=C7=D6=D8=B5=FE=A1=A3<BR><BR>PROGRAM=20
NAME: range<BR><BR>INPUT FORMAT<BR><BR>=B5=DA 1 =
=D0=D0:<BR>=A1=A1=A1=A1N,=C4=C1=C7=F8=B5=C4=B1=DF=B3=A4=A1=A3<BR><BR>=B5=DA=
2=20
=B5=BD=A1=A1n+1=D0=D0: =
<BR>N=B8=F6=C3=BB=D3=D0=BF=D5=B8=F1=B7=D6=BF=AA=B5=C4=D7=D6=B7=FB=A1=A3<B=
R><BR>0 =B1=ED=CA=BE =
"=C4=C7=D2=BB=B8=F6=C7=F8=B6=CE=B1=BB=BB=D9=BB=B5=C1=CB";1 =B1=ED=CA=BE =
"=20
=D7=BC=B1=B8=BA=C3=B1=BB=B3=D4"=A1=A3<BR><BR><BR>SAMPLE INPUT =
(file range.in)=20
=
<BR>6<BR>101111<BR>001111<BR>111111<BR>001111<BR>101101<BR>111001<BR><BR>=
OUTPUT=20
=
FORMAT<BR>=CA=E4=B3=F6=C4=C7=D0=A9=B4=E6=D4=DA=B5=C4=D5=FD=B7=BD=D0=CE=B5=
=C4=B4=F3=D0=A1=BA=CD=B8=F6=CA=FD=A3=AC=D2=BB=D6=D6=D2=BB=D0=D0=A1=A3<BR>=
<BR>SAMPLE OUTPUT (file=20
range.out)<BR>2 10<BR>3 4<BR>4 1</DIV>
<HR>
<P><STRONG>USACO 3.3.4 Home on the =
Range<BR>=CC=E1=BD=BB=B4=CE=CA=FD:1=B4=CE</STRONG></P>
=
<P><STRONG>=D5=E2=B4=CE=BF=B4=B5=BD=CA=FD=BE=DD=D0=A1,=CB=F9=D2=D4=CA=FD=D7=
=E9=BF=AA=C1=CBlongint,ac=BA=F3=BF=B4=B5=BD=B9=FB=C8=BB=BF=C9=C4=DC=B3=F6=
=CF=D6=D3=D0longint=B5=C4...</STRONG></P>
=
<P><STRONG>=B5=DA=B6=FE=B4=CE=D7=F6=C1=CB,DP=BD=E9=C9=DC=C7=EB=BF=B4=C9=CF=
=D2=BB=B4=CE=D7=F6=B5=C4=C8=D5=D6=BE:</STRONG></P>
<P><A=20
=
href=3D"http://hi.baidu.com/leokan/blog/item/62d80133f74725fb1a4cffdb.htm=
l"><STRONG>http://hi.baidu.com/leokan/blog/item/62d80133f74725fb1a4cffdb.=
html</STRONG></A></P>
<P><STRONG>{<BR>TASK:range<BR>LANG:PASCAL<BR>}<BR>program=20
range;<BR>const<BR> =20
maxn=3D250;<BR>var<BR> =
f,r,d:array[1..maxn+1,1..maxn+1] of=20
integer;<BR> map:array[1..maxn,1..maxn] of=20
char;<BR> count:array[1..maxn] of=20
longint;<BR> n:integer;<BR>procedure=20
init;<BR>var<BR> =20
i,j:integer;<BR>begin<BR> =20
assign(input,'range.in');reset(input);<BR> =20
readln(n);<BR> for i:=3D1 to n=20
do<BR> =20
=
begin<BR> &nbs=
p;=20
for j:=3D1 to n=20
=
do<BR> &=
nbsp; =20
=
read(map[i,j]);<BR> =
=20
readln;<BR> =20
end;<BR> close(input);<BR>end;<BR>function=20
minof3(x,y,z:integer):integer;<BR>begin<BR> if =
x>y=20
then<BR> =20
=
begin<BR> &nbs=
p;=20
if y>z then=20
=
exit(z)<BR> &n=
bsp;=20
else exit(y);<BR> =20
end<BR> else=20
=
begin<BR> &nbs=
p;=20
if x>z then=20
=
exit(z)<BR> &n=
bsp;=20
else exit(x);<BR> =20
end;<BR>end;<BR>procedure dp;<BR>var<BR> =20
i,j,k:integer;<BR>begin<BR> =20
assign(output,'range.out');rewrite(output);<BR> =
for i:=3Dn=20
downto 1 do<BR> for =
j:=3Dn downto=20
1 =
do<BR> =
if map[i,j]=3D'1'=20
=
then<BR>  =
; =20
=
begin<BR> &nbs=
p; =20
=
r[i,j]:=3Dr[i,j+1]+1;<BR> =
=20
=
d[i,j]:=3Dd[i+1,j]+1;<BR> =
=20
=
f[i,j]:=3Dminof3(f[i+1,j+1]+1,r[i,j],d[i,j]);<BR> =
&=
nbsp; =20
for k:=3Df[i,j] downto 2=20
=
do<BR> &=
nbsp; =20
=
inc(count[k]);<BR> &=
nbsp; =20
end;<BR> for i:=3D2 to n=20
do<BR> if count[i]>0=20
=
then<BR>  =
;=20
writeln(i,' ',count[i]);<BR> =20
close(output);<BR>end;<BR>begin<BR> =20
init;<BR> dp;<BR>end.</STRONG></P><STRONG>
<HR>
</STRONG>
<P><STRONG>USACO=B5=C4=B7=D6=CE=F6</STRONG></P>
<P><STRONG>To count the squares, we first precompute the biggest =
square=20
with lower right corner at any particular location. This is done =
by=20
dynamic programming: the biggest square with lower right corner at =
(i, j)=20
is the minimum of three numbers: </STRONG></P>
<UL>
<LI><STRONG>the number of consecutive uneaten grid units to the =
left=20
</STRONG>
<LI><STRONG>the number of consecutive uneaten grid units to the =
right=20
</STRONG>
<LI><STRONG>one plus the size of the biggest square with lower =
right=20
corner at (i-1, j-1) </STRONG></LI></UL>
<P><STRONG>Once we've computed this information, counting squares =
is=20
simple: go to each lower right corner and increment the counters =
for every=20
square size between 2 and the biggest square ending at that =
corner.=20
</STRONG></P><PRE><STRONG>#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#define MAXN 250
int goodsq[MAXN][MAXN];
int bigsq[MAXN][MAXN];
int tot[MAXN+1];
int
min(int a, int b)
{
return a < b ? a : b;
}
void
main(void)
{
FILE *fin, *fout;
int i, j, k, l, n, sz;
fin =3D fopen("range.in", "r");
fout =3D fopen("range.out", "w");
assert(fin !=3D NULL && fout !=3D NULL);
fscanf(fin, "%d\n", &n);
for(i=3D0; i<n; i++) {
for(j=3D0; j<n; j++)
goodsq[i][j] =3D (getc(fin) =3D=3D '1');
assert(getc(fin) =3D=3D '\n');
}
/* calculate size of biggest square with lower right corner (i,j) */
for(i=3D0; i<n; i++) {
for(j=3D0; j<n; j++) {
for(k=3Di; k>=3D0; k--)
if(goodsq[k][j] =3D=3D 0)
break;
for(l=3Dj; l>=3D0; l--)
if(goodsq[i][l] =3D=3D 0)
break;
sz =3D min(i-k, j-l);
if(i > 0 && j > 0)
sz =3D min(sz, bigsq[i-1][j-1]+1);
bigsq[i][j] =3D sz;
}
}
/* now just count squares */
for(i=3D0; i<n; i++)
for(j=3D0; j<n; j++)
for(k=3D2; k<=3Dbigsq[i][j]; k++)
tot[k]++;
for(i=3D2; i<=3Dn; i++)
if(tot[i])
fprintf(fout, "%d %d\n", i, tot[i]);
=20
exit(0);
}
</STRONG></PRE>
<P><STRONG>Greg Price writes: </STRONG></P>
<P><STRONG>The posted solution runs in cubic time, with quadratic =
storage.=20
With a little more cleverness in the dynamic programming, the task =
can be=20
accomplished with only quadratic time and linear storage, and the =
same=20
amount of code and coding effort. Instead of running back along =
the rows=20
and columns from each square, we use the biggest-square values =
immediately=20
to the west and north, so that each non-ravaged square's =
biggest-square=20
value is one more than the minimum of the values to the west, =
north, and=20
northwest. This saves time, bringing us from cubic to quadratic =
time.=20
</STRONG></P>
<P><STRONG>Another improvement, which saves space and perhaps =
cleans up=20
the code marginally, is to keep track of the number of squares of =
a given=20
size as we go along. This obviates the need to keep a =
quadratic-size=20
matrix of biggest-square values, because we only need the most =
recent row=20
for continuing the computation. As for "ravaged" values, we only =
use each=20
one once, all in order; we can just read those as we need them.=20
</STRONG></P><PRE><STRONG>#include <fstream.h>
ifstream fin("range.in");
ofstream fout("range.out");
const unsigned short maxn =3D 250 + 5;
unsigned short n;
char fieldpr;
unsigned short sq[maxn]; // biggest-square values
unsigned short sqpr;
unsigned short numsq[maxn]; // number of squares of each size
unsigned short
min3(unsigned short a, unsigned short b, unsigned short c)
{
if ((a <=3D b) && (a <=3D c))
return a;
else=20
return (b <=3D c) ? b : c;
}
void
main()
{
unsigned short r, c;
unsigned short i;
unsigned short tmp;
fin >> n;
for (c =3D 1; c <=3D n; c++)
sq[c] =3D 0;
for (i =3D 2; i <=3D n; i++)
numsq[i] =3D 0;
for (r =3D 1; r <=3D n; r++)
{
sqpr =3D 0;
sq[0] =3D 0;
for (c =3D 1; c <=3D n; c++)
{
fin >> fieldpr;
if (!(fieldpr - '0'))
{
sqpr =3D sq[c];
sq[c] =3D 0;
continue;
}
// Only three values needed.
tmp =3D 1 + min3(sq[c-1], sqpr, sq[c]);
sqpr =3D sq[c];
sq[c] =3D tmp;
// Only count maximal squares, for now.
if (sq[c] >=3D 2)
numsq[ sq[c] ]++;
}
}
// Count all squares, not just maximal.=20
for (i =3D n-1; i >=3D 2; i--)
numsq[i] +=3D numsq[i+1];
for (i =3D 2; i <=3D n && numsq[i]; i++)
fout << i << ' ' << numsq[i] << endl;
}
</pre></STRONG></PRE></DIV></TD></TR></TBODY></TABLE><BR>
<DIV class=3Dopt><A =
title=3D=B2=E9=BF=B4=B8=C3=B7=D6=C0=E0=D6=D0=CB=F9=D3=D0=CE=C4=D5=C2=20
href=3D"http://hi.baidu.com/leokan/blog/category/Oi">=C0=E0=B1=F0=A3=BAOi=
</A> | <A=20
title=3D=BD=AB=B4=CB=CE=C4=D5=C2=CC=ED=BC=D3=B5=BD=B0=D9=B6=C8=CB=D1=B2=D8=
onclick=3D"return addToFavor();"=20
href=3D"http://cang.baidu.com/do/add" =
target=3D_blank>=CC=ED=BC=D3=B5=BD=CB=D1=B2=D8</A> | =E4=AF=C0=C0(<SPAN=20
id=3Dresult></SPAN>) | <A=20
href=3D"http://hi.baidu.com/leokan/blog/item/58628ccb6c8ecff953664f75.htm=
l#send">=C6=C0=C2=DB</A> (0)
<SCRIPT language=3Djavascript>
/*<![CDATA[*/
var pre =3D [true,'USACO 3.3.3 Camelot =CC=E2=BD=E2', 'USACO 3.3.3 =
Camelot =
=CC=E2=BD=E2','/leokan/blog/item/5ff69f58f138cada9c820489.html'];
var post =3D [true,'USACO 3.3.5 A Game =CC=E2=BD=E2','USACO 3.3.5 A Game =
=CC=E2=BD=E2', '/leokan/blog/item/dcda8835e62c9e1591ef39c9.html'];
if(pre[0] || post[0]){
document.write('<div =
style=3D"height:5px;line-height:5px;"> </div><div id=3D"in_nav">');
if(pre[0]){
document.write('=C9=CF=D2=BB=C6=AA=A3=BA<a href=3D"' + pre[3] + '" =
title=3D"' + pre[1] + '">' + pre[2] + '</a> ');
}
if(post[0]){
document.write('=CF=C2=D2=BB=C6=AA=A3=BA<a href=3D"' + post[3] + '" =
title=3D"' + post[1] + '">' + post[2] + '</a>');
}
document.write('</div>');
}
/*]]>*/
</SCRIPT>
</DIV>
<DIV class=3Dline></DIV>
<STYLE type=3Dtext/css>#in_related_doc A {
TEXT-DECORATION: none
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -