Welcome To SDIBT ACM-ICPC Online Judge

VIRTUAL JUDGE Recent Contest F.A.Qs Discuss Home ProblemSet Status Ranklist 2 Contest LoginRegister Exam
SDIBT Online Judge WebBoard
[ New Thread ]
Problem 2353 >> 注意点
jk11171228 @ 2013-09-19 18:23:21
[ Quote ] [ Edit ] [ Delete ] 1#
1.首先给出的先是列后是行,做的时候注意;
2.题目有个地方写错了,不是玩家必须选择一个骑士跟国王一起行动,原题的意思是,当一个骑士跟国王在一个格子的时候,
可以带着国王一起走。



3.本题的思路。。还是看解题才想到的。。。
开个四维的数组dis[a][b][c][d],表示(a,b)到(c,d)的最短距离。枚举最后的集中点(i,j),sum表示骑士到集中点的距离
和,则国王如果不跟骑士一起走,到集中点的距离是max(abs(kingx-i),abs(kingy-j))。。现在枚举如果跟战士k一起走的话,则说明要k先要到国王处,然后再到终点。。这样的距离就是sum-dis[i][j][x[k]][y[k]]+dis[x[k]][y[k]][kingx+dx][kingy+dy]+dis[kingx+dx][kingy+dy][i][j]+max(dx,dy);最后比较大小即可。。
[Top]  [Previous]  [Next]

HOME Back

한국어 中文 English
All Copyright Reserved 2008-2010 SDIBT TEAM
GPL2.0 2003-2010 HUSTOJ Project TEAM
Anything about the Problems, Please Contact Admin:admin