原题:
在8*8的棋盘上分布着n个骑士,他们想约在某一格中聚会.骑士每天可以像国际象棋中的马那样移动一次.请你计算n个骑士的最早聚会地点和要走多少天.要求尽早聚会,且n个人走的总步数最少,先到的骑士可以不再移动等待其它骑士.
输入:
从键盘输入n(0<n<=64),然后依次输入n个骑士的初始位置xi,yi(0<=xi,yi<=7)
输出
:以空格分隔的三个整数,分别为聚会点的x,y值,以及要走多少天
对问题的分析:为了解决这个问题,显然我们得想办法能计算出骑士从棋盘上的某个格子到其它格子需要的最少步数.
(另一方面,很容易可以证明骑士可以从棋盘上任意一个格子到达另一个格子)当然,最直接的想法是用搜索,挨个试一遍就OK了.
这也是种方法,如果加上动态规划,也是可行的算法.不过这里我没用这种方法,而是采用图论算法中已有的用于计算一个图中任意两点最短路径的经典算法--Floyd-Warshall算法.
我们可以将棋盘的64个格子看成64个节点,其中两个节点中存在一条边相连当且仅当骑士可以直接从其中的一个节点跳到另一个节点.这样骑士从棋盘某点到另一点需要移动的最少次数就转化为计算这个图中两个节点的最短路问题.至于Floyd-Warshall算法我就不多说了,随便baidu一下就知道.
剩下的问题就好办了,下面是我写的JAVA代码:
java 代码
-
-
-
-
-
-
-
-
- import
java.util.Scanner;
- public
class
Main{
-
public
static
void
main(String[] args){
- Scanner scan =
new
Scanner(System.in);
-
int
n =scan.nextInt();
-
int
[][] pos =
new
int
[n][
2
];
-
for
(
int
index =
0
;index<n;index ++){
- pos[index][
0
] =scan.nextInt();
- pos[index][
1
] =scan.nextInt();
- }
- ResultInf result =
new
Knight().solve(pos);
- System.out.print(result.x +
" "
+result.y +
" "
+result.days);
- }
- }
-
- class
Knight{
-
private
static
final
int
DEFAULT_SIZE =
8
;
-
-
private
int
boardSize;
-
-
-
private
int
[][] dist;
-
-
-
-
-
public
Knight(
int
boardSize){
-
this
.boardSize =boardSize;
- initDist();
- }
-
public
Knight(){
-
this
(DEFAULT_SIZE);
- }
-
-
-
-
-
-
public
ResultInf solve(
int
[][] pos){
-
if
(pos ==
null
||pos.length ==
0
|| pos[
0
].length !=
2
)
throw
new
IllegalArgumentException();
-
int
location =
0
,days =Integer.MAX_VALUE,allDays =
0
;
-
for
(
int
n =
0
;n<boardSize*boardSize;n ++){
-
int
max =
0
,sum =
0
;
-
for
(
int
index =
0
;index<pos.length;index ++){
-
int
dis = dist[n][pos[index][
0
]+pos[index][
1
]*boardSize];
- sum += dis;
-
if
(max<dis) max =dis;
- }
-
if
(days>max ||(days==max&&allDays>sum)){
- days =max;
- allDays =sum;
- location =n;
- }
- }
-
return
new
ResultInf(location%boardSize,location/boardSize,days);
- }
-
-
-
-
private
void
initDist(){
-
int
count =boardSize*boardSize;
- dist =
new
int
[count][count];
-
for
(
int
n =
0
;n<count;n++)
-
for
(
int
m =
0
;m<count;m++)
-
if
(m!=n) dist[m][n] = isConnect(m%boardSize,m/boardSize,n%boardSize,n/boardSize)?
1
: Integer.MAX_VALUE;
-
-
for
(
int
k =
0
;k<count;k++)
-
for
(
int
n =
0
;n<count;n++)
-
for
(
int
m =
0
;m<count;m++)
-
if
(dist[n][k]<Integer.MAX_VALUE&&dist[k][m]<Integer.MAX_VALUE&&
- dist[n][k]+dist[k][m] <dist[n][m])
- dist[n][m] =dist[n][k] +dist[k][m];
- }
-
-
-
-
private
boolean
isConnect(
int
x1,
int
y1,
int
x2,
int
y2){
-
return
(x1!=x2&&y1!=y2&&Math.abs(x1-x2)+Math.abs(y1-y2)==
3
);
- }
- }
-
-
-
-
- class
ResultInf{
-
public
int
x,y,days;
-
public
ResultInf(
int
x,
int
y,
int
days){
-
this
.x =x;
-
this
.y =y;
-
this
.days =days;
- }
- }
这个是C++版:
cpp 代码
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- #include<iostream>
- #define X(n) ((n)&7)
- #define Y(n) ((n)>>3)
- #define P(x,y) ((x)+((y)<<3))
- #define ABS(x) ((x)>=0?(x):-(x))
-
-
- const
int
SIZE = 8;
-
-
- const
int
INFINITY = 2*SIZE*SIZE;
-
-
-
- int
dest[SIZE*SIZE][SIZE*SIZE];
-
-
-
-
- bool
connected(
int
m,
int
n){
-
int
x1 =X(m), y1 =Y(m);
-
int
x2 =X(n), y2 =Y(n);
-
return
( (ABS(x1-x2)==2&&ABS(y1-y2)==1)||
- (ABS(x1-x2)==1&&ABS(y1-y2)==2)
- );
- }
-
-
-
-
- void
init(){
-
-
-
for
(
int
m =0;m< SIZE*SIZE; m++)
-
for
(
int
n =0;n< SIZE*SIZE; n++)
-
if
(m == n) dest[m][n] = 0;
-
else
dest[m][n] = connected(m,n)? 1: INFINITY;
-
-
-
for
(
int
k=0;k< SIZE*SIZE; k++)
-
for
(
int
m=0;m< SIZE*SIZE; m++)
-
for
(
int
n=0;n< SIZE*SIZE; n++)
-
if
(dest[m][n] >dest[m][k]+dest[k][n])
- dest[m][n] =dest[m][k]+dest[k][n];
- }
-
- int
main(){
- init();
-
int
size;
- std::cin>>size;
-
int
*pos =
new
int
[size];
-
for
(
int
i =0;i<size;i++){
-
int
x,y;
- std::cin>>x>>y;
- pos[i] =P(x,y);
- }
-
int
days =INFINITY,allDays,location;
-
for
(
int
m =0;m<SIZE*SIZE;m++){
-
int
max =0,sum =0;
-
for
(
int
k =0;k<size;k++){
- sum += dest[m][pos[k]];
-
if
(dest[m][pos[k]] >max) max =dest[m][pos[k]];
- }
-
if
(max<days ||(max ==days&&sum<allDays) ){
- days =max;
- allDays =sum;
- location =m;
- }
- }
-
delete
[] pos;
- std::cout<<X(location)<<
" "
<<Y(location)<<
" "
<<days;
-
return
0;
- }
分享到:
- 2007-09-16 00:42
- 浏览 3150
- 评论(2)
- 论坛回复 / 浏览 (2 / 4059)
- 查看更多
相关推荐
《程序员》第9期智慧擂台题目文件
《程序员》9期算法擂台“骑士聚会”源代码
围绕“面试”、“算法”、“编程”三个主题的程序员编程艺术系列(简称TAOPP系列),从今年4月写第一篇起,至今快有一年。近1年的创作中,写了二十七章,共计22篇文章。这是本人的第4大原创作品,不过与之前微软面试...
程序员实用算法+源码,本书一共七个部分全部下载才可正常解压
• 第六章 海量数据处理 o 6.0 本章导读 o 6.1 关联式容器 o 6.2 分而治之 o 6.3 simhash 算法 o 6.4 外排序 o 6.5 MapReduce o 6.6 多层划分 o 6.7 Bitmap o 6.8 Bloom filter o 6.9 Trie 树 o 6.10 数据库 o 6.11 ...
2009年程序员杂志第九期 (希望大家有收获)
程序员代码面试指南 IT名企算法与数据结构题目最优解,算法全部代码,非常优秀,算法精妙,题目经典,欢迎下载。
程序员代码面试指南 IT名企算法与数据结构题目最优解(书中代码)
程序员实用算法
程序员实用算法 程序员实用算法程序员实用算法 程序员实用算法
程序员06第9期 免分
PHP程序员算法题汇总,经典算法题仅供学习研究。
程序员06第1期 程序员06第1期
程序员实用算法源码兼容VS2008及更高级的版本。在VS2008中可以直接运行,在VS2010中需先进行转换才能运行。 每个项目文件中,具体参数如何设置,是可以从源码的main函数中获得的,具体可以查看main函数中形如“...
程序员06第2期 程序员06第2期
2006程序员第九期
程序员2006年第9期PDF.rar
程序员06第3期 程序员06第3期 免分
程序员06第9期.pdf
优秀程序员必须知道的32个算法