[2017年整理]POJ 1178 Camlot.ppt

下载文档 降价啦

3
0
约1.88千字
约 7页
2017-05-06 发布于浙江
举报
版权申诉
保障服务

[2017年整理]POJ 1178 Camlot.ppt

1、本文档共7页，可阅读全部内容。
2、有哪些信誉好的足球投注网站（book118）网站文档一经付费（服务费），不意味着购买了该文档的版权，仅供个人/单位学习、研究之用，不得用于商业用途，未经授权，严禁复制、发行、汇编、翻译或者网络传播等，侵权必究。
3、本站所有内容均由合作方或网友上传，本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺！文档内容仅供研究参考，付费前请自行鉴别。如您付费，意味着您自己接受本站规则且自行承担风险，本站不退款、不进行额外附加服务；查看《如何避免下载的几个坑》。如果您已付费下载过本站文档，您可以点击这里二次下载。
4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等，请点击“版权申诉”（推荐），也可以打举报电话：400-050-0827(电话支持时间：9:00-18:30)。

[2017年整理]POJ 1178 Camlot

Camlot 解题报告IOI’98 Day 2 Problem 2 赵静 2003年7月12日游戏描述初始状态：一个国王和N个骑士分布在8*8的棋盘上 0 = N = 63 目标状态：国王和所有的骑士走到同一个格子里游戏规则：在一次移动中，国王可以走到相邻的八个格子里骑士可以走八个方向的“日”字国王和某个骑士相遇后，可以由骑士带着移动任务：用最少的总移动步数达到目标状态。 Sample 分析最短路问题求一个点，使其到已知若干点的总路径最短点的个数有限（64个），逐个枚举国王和骑士相遇的特殊情形国王可能和任意一个骑士在任意一点相遇枚举63 * 64种可能枚举法预处理：用Floyd算法求出骑士在任意两点间的最短路径枚举过程：O ( 64 * 64 * N) ans = INT_MAX; for ( i 取遍棋盘上的64个点) { sum = 每个骑士到 i 的距离之和; for ( j 取遍棋盘上的64个点) { tmp1 = 国王到点 j 的距离; // 怎样计算？ tmp2 = min { 骑士 k 经过 j 到 i 的距离 - 骑士 k 到 i 的距离 }; // k 取遍所有骑士 ans = min {ans, sum + tmp1 + tmp2}; } } 递推算法（供参考） CK [ i ] [ j ] 骑士从 i 到 j 的距离 CKK [ i ] [ j ] 国王从 i 到 j 的距离 CG [ i ] = sum { CK [ knight [ j ] ] [ i ] }，j 取遍所有骑士所有骑士在 i 相遇的总距离 MKK [ i ] [ j ] = CK [ knight [ i ] ] [ j ] + CKK [ king ] [ j ] 国王和第 i 个骑士在 j 相遇的距离 MKM [ i ] [ j ] = min { MKK [ i ] [ k ] + CK [ k ] [ j ] + CG [ j ] – CK [ knight [ i ] ] [ j ] } 第 i 个骑士带着国王和其它骑士在 j 相遇的总距离 ans = min { MKM [ i ] [ j ] }，i 取遍所有骑士，j 取遍64个点 THE END Thank you for your attention! * * Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. D4A3A8H1H8 Input: 10 Output: A B C D E F G H 8 7 6 5 4 3 2 1 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd.