📄 usaco 3_3_3 camelot 题解_leokan的blog.mht
字号:
assign(input,'camelot.in');reset(input);<BR> =20
readln(r,c);<BR> =
readln(s);<BR> =20
king[1]:=3Dord(s[3])-48;<BR> =20
king[2]:=3Dord(s[1])-64;<BR> =
n:=3D0;<BR> =20
while not eof do<BR> =20
readline;<BR> close(input);<BR>end;<BR>procedure =
spfa(x,y:integer);<BR>var<BR> =20
i,open,close:integer;<BR> queue:array[1..maxq] =
of=20
seat;<BR> inqueue:array[1..40,1..26] of=20
boolean;<BR> =
now:seat;<BR>begin<BR> =20
fillchar(queue,sizeof(queue),0);<BR> =20
fillchar(inqueue,sizeof(inqueue),0);<BR> =20
dis[x,y,x,y]:=3D0;<BR> =20
queue[1,1]:=3Dx;<BR> =
queue[1,2]:=3Dy;<BR> =20
inqueue[x,y]:=3Dtrue;<BR> =
open:=3D0;<BR> =20
close:=3D1;<BR> while open<>close=20
do<BR> =20
=
begin<BR> &nbs=
p;=20
=
inc(open);<BR>  =
; =20
if open>maxq then=20
=
dec(open,maxq);<BR> =
=20
=
now:=3Dqueue[open];<BR> &n=
bsp; =20
for i:=3D1 to 8=20
=
do<BR> &=
nbsp; =20
if not=20
=
inqueue[now[1]+nexta[i],now[2]+nextb[i]]and(now[1]+nexta[i]>0)and(now[=
1]+nexta[i]<=3Dr)and(now[2]+nextb[i]>0)and(now[2]+nextb[i]<=3Dc)=
then<BR>  =
; =20
if=20
=
(dis[x,y,now[1]+nexta[i],now[2]+nextb[i]]=3D-1)or(dis[x,y,now[1]+nexta[i]=
,now[2]+nextb[i]]>dis[x,y,now[1],now[2]]+1)=20
=
then<BR>  =
; =
=20
=
begin<BR> &nbs=
p;  =
; =20
=
dis[x,y,now[1]+nexta[i],now[2]+nextb[i]]:=3Ddis[x,y,now[1],now[2]]+1;<BR>=
&=
nbsp; &n=
bsp; =20
=
inc(close);<BR> &nbs=
p;  =
; =20
if close>maxq then=20
=
dec(close,maxq);<BR>  =
; =
=20
=
queue[close,1]:=3Dnow[1]+nexta[i];<BR>  =
; =
=20
=
queue[close,2]:=3Dnow[2]+nextb[i];<BR>  =
; =
=20
=
inqueue[now[1]+nexta[i],now[2]+nextb[i]]:=3Dtrue;<BR> &n=
bsp; &nb=
sp; =20
=
end;<BR>  =
;=20
=
inqueue[now[1],now[2]]:=3Dfalse;<BR> &=
nbsp;=20
end;<BR>end;<BR>procedure initdis;<BR>var<BR> =20
i,j:integer;<BR>begin<BR> =20
fillchar(dis,sizeof(dis),255);<BR> for i:=3D1 to =
r=20
do<BR> for j:=3D1 to c=20
=
do<BR> =
spfa(i,j);<BR>end;<BR>function=20
maxof2(x,y:integer):integer;<BR>begin<BR> if =
x<y then=20
exit(y)<BR> else exit(x);<BR>end;<BR>function=20
kingmove(x1,y1:integer):integer;<BR>begin<BR> =20
=
exit(maxof2(abs(x1-king[1]),abs(y1-king[2])));<BR>end;<BR>procedure=20
work;<BR>var<BR> =20
i,j,l,m,k:integer;<BR> =20
min,sum:integer;<BR>begin<BR> =20
=
assign(output,'camelot.out');rewrite(output);<BR> if =
n=3D0=20
then<BR> =20
=
begin<BR> &nbs=
p;=20
=
writeln(0);<BR> &nbs=
p; =20
=
close(output);<BR> &=
nbsp; =20
exit;<BR> =20
end;<BR> min:=3Dmaxint;<BR> if =
n=3D1=20
then<BR> =20
=
begin<BR> &nbs=
p;=20
for l:=3Dking[1]-3 to king[1]+3=20
=
do<BR> &=
nbsp; =20
for m:=3Dking[2]-3 to king[2]+3=20
=
do<BR> &=
nbsp; =20
=
begin<BR> &nbs=
p;  =
; =20
if (l<=3D0)or(l>r)or(m<=3D0)or(m>c) then=20
=
continue;<BR> =
&=
nbsp; =20
if=20
=
(dis[knight[1,1],knight[1,2],l,m]>=3D0)and(kingmove(l,m)+dis[knight[1,=
1],knight[1,2],l,m]<min)=20
=
then<BR>  =
; =
=20
=
min:=3Dkingmove(l,m)+dis[knight[1,1],knight[1,2],l,m];<BR> &nb=
sp; &nbs=
p; =20
=
end;<BR>  =
;=20
=
writeln(min);<BR> &n=
bsp; =20
=
close(output);<BR> &=
nbsp; =20
exit;<BR> =20
end;<BR> for i:=3D1 to r=20
do<BR> for j:=3D1 to c=20
=
do<BR> =
=
begin<BR> &nbs=
p; =20
=
sum:=3D0;<BR> =
=20
for k:=3D1 to n=20
=
do<BR> &=
nbsp; =20
=
inc(sum,dis[knight[k,1],knight[k,2],i,j]);<BR> &nb=
sp; =20
if sum>min then=20
=
continue;<BR> =
=20
for l:=3Dking[1]-2 to king[1]+2=20
=
do<BR> &=
nbsp; =20
for m:=3Dking[2]-2 to king[2]+2=20
=
do<BR> &=
nbsp; =20
=
begin<BR> &nbs=
p;  =
; =20
if (l<=3D0)or(l>r)or(m<=3D0)or(m>c) then=20
=
continue;<BR> =
&=
nbsp; =20
for k:=3D1 to n=20
=
do<BR> &=
nbsp; &n=
bsp; =20
if=20
=
(dis[knight[k,1],knight[k,2],i,j]>=3D0)and(dis[l,m,i,j]>=3D0)and(di=
s[knight[k,1],knight[k,2],l,m]>=3D0)and(sum-dis[knight[k,1],knight[k,2=
],i,j]+dis[knight[k,1],knight[k,2],l,m]+dis[l,m,i,j]+kingmove(l,m)<min=
)=20
=
then<BR>  =
; =
=
=
min:=3Dsum-dis[knight[k,1],knight[k,2],i,j]+dis[knight[k,1],knight[k,2],l=
,m]+dis[l,m,i,j]+kingmove(l,m);<BR> &n=
bsp; &nb=
sp; =20
=
end;<BR>  =
;=20
end;<BR> writeln(min);<BR> =20
close(output);<BR>end;<BR>begin<BR> =20
init;<BR> initdis;<BR> =20
work;<BR>end.<BR></STRONG>
<P></P>
<P><STRONG></STRONG></P>
<P><STRONG>This is a modification of the shortest path algorithm. =
If there=20
was no king, then the shortest path algorithm can determine the =
distance=20
that each knight must travel to get to each square. Thus, the cost =
of=20
gathering in a particular square is simply the sum of the distance =
that=20
each knight must travel, which is fairly simple to calculate.=20
</STRONG></P>
<P><STRONG>In order to consider the king, consider a knight which=20
'picks-up' the king in some square and then travels to the =
gathering spot.=20
This costs some number of extra moves than just traveling to the =
gathering=20
spot. In particular, the king must move to the pick-up square, and =
the=20
knight must travel to this square and then to the final gathering =
point.=20
Consider the number of extra moves to be the `cost' for that =
knight to=20
pick-up the king. It is simple to alter the shortest path =
algorithm to=20
consider picking-up the king by augmenting the state with a =
boolean flag=20
stating whether the knight has the king or not. </STRONG></P>
<P><STRONG>In this case, the cost for gathering at a particular =
location=20
is the sum of the distance that each knight must travel to get to =
that=20
square plus the minimum cost for a knight picking up the king on =
the way.=20
</STRONG></P>
<P><STRONG>Thus, for each square, we keep two numbers, the sum of =
the=20
distance that all the knights that we have seen thus far would =
have to=20
travel to get to this square and the minimum cost for one of those =
knights=20
picking up the king on the way (note that one way to 'pick-up' the =
king is=20
to have the king travel all by itself to the gathering spot). =
Then, when=20
we get a new knight, we run the shortest path algorithm and add =
the cost=20
of getting that knight (without picking up the king) to each =
square to the=20
cost of gathering at that location. Additionally, for each square, =
we=20
check if the new knight can pick-up the king in fewer moves than =
any=20
previous knight, and update that value if it can. </STRONG></P>
<P><STRONG>After all the knights have been processed, we determine =
the=20
minimum over all squares of the cost to get to that square plus =
the=20
additional cost for a knight to pick-up the king on its way to =
that=20
square. </STRONG></P><PRE><STRONG>#include <stdio.h>
#include <string.h>
#include <stdlib.h>
/* "infinity"... > maximum distance possible (for one knight) */
#define MAXN 10400
/* maximum number of rows */
#define MAXR 40=20
/* maximum number of columns */
#define MAXC 26=20
/* cost of collecting all knights here */
int cost[MAXC][MAXR];=20
/* cost of getting a knight to collect the king */
int kingcost[MAXC][MAXR];
/* distance the king must travel to get to this position */
int kdist[MAXC][MAXR];
/* distance to get for current knight to get to this square */
/* third index: 0 =3D> without king, 1 =3D> with king */
int dist[MAXC][MAXR][2];=20
/* number of rows and columns */
int nrow, ncol;
int do_step(int x, int y, int kflag) {
int f =3D 0; /* maximum distance added */
int d =3D dist[x][y][kflag]; /* distance of current move */
/* go through all possible moves that a knight can make */
if (y > 0) {
if (x > 1)
if (dist[x-2][y-1][kflag] > d+1) {
dist[x-2][y-1][kflag] =3D d+1;
f =3D 1;
}
if (x < ncol-2) {
if (dist[x+2][y-1][kflag] > d+1) {
dist[x+2][y-1][kflag] =3D d+1;
f =3D 1;
}
}
if (y > 1) {
if (x > 0)
if (dist[x-1][y-2][kflag] > d+1) {
dist[x-1][y-2][kflag] =3D d+1;
f =3D 1;
}
if (x < ncol-1)
if (dist[x+1][y-2][kflag] > d+1) {
dist[x+1][y-2][kflag] =3D d+1;
f =3D 1;
}
}
}
if (y < nrow-1) {
if (x > 1)
if (dist[x-2][y+1][kflag] > d+1) {
dist[x-2][y+1][kflag] =3D d+1;
f =3D 1;
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -