《程序员》2007第九期之算法擂台

原题: 在8*8的棋盘上分布着n个骑士,他们想约在某一格中聚会.骑士每天可以像国际象棋中的马那样移动一次.请你计算n个骑士的最早聚会地点和要走多少天.要求尽早聚会,且n个人走的总步数最少,先到的骑士可以不再移动等待其它骑士.

输入: 从键盘输入n(0＜ｎ＜=64)，然后依次输入n个骑士的初始位置xi，yi(0＜＝xi,yi＜＝７)

输出 :以空格分隔的三个整数,分别为聚会点的x,y值,以及要走多少天

       对问题的分析:为了解决这个问题,显然我们得想办法能计算出骑士从棋盘上的某个格子到其它格子需要的最少步数.
(另一方面,很容易可以证明骑士可以从棋盘上任意一个格子到达另一个格子)当然,最直接的想法是用搜索,挨个试一遍就OK了.
这也是种方法,如果加上动态规划,也是可行的算法.不过这里我没用这种方法,而是采用图论算法中已有的用于计算一个图中任意两点最短路径的经典算法--Floyd-Warshall算法.
        我们可以将棋盘的64个格子看成64个节点,其中两个节点中存在一条边相连当且仅当骑士可以直接从其中的一个节点跳到另一个节点.这样骑士从棋盘某点到另一点需要移动的最少次数就转化为计算这个图中两个节点的最短路问题.至于Floyd-Warshall算法我就不多说了,随便baidu一下就知道.
       剩下的问题就好办了,下面是我写的JAVA代码:

java 代码

/**
   &#Main.java
   ＜程序员＞2007第九期算法擂台之JAVA代码
   注: 该问题的解未必唯一,但根据问题需要,只给出一个解
   另: 经测试,运行1000次new Knight()大约耗时6000毫秒
   @author Eastsun
   @version 1.0 2007/9/3
*/
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;

    
//dis[i][j]表示骑士从棋盘上位置i到j所需的最少步数,其中位置i对于棋盘坐标(i%boardSize,i/boardSize)
    
private
 
int
[][] dist;
    
/**
       Knight的构造函数
       @param boardSize 棋盘的大小,默认值为8
    */
    
public
 Knight(
int
 boardSize){
        
this
.boardSize =boardSize;
        initDist();
    }
    
public
 Knight(){
        
this
(DEFAULT_SIZE);
    }
    
/**
       根据骑士的位置求解
       @param pos 一个int[][2]数组,第k个骑士的位置为(pos[k][0],pos[k][1])
       @return result 该问题的解,注意:当result.days ==Integer.MAX_VALUE的时候说明这些骑士永远不可能聚在一起
    */
    
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);
    }
    
/**
       使用Floyd-Warshall算法计算dist的值,时间复杂度O(boardSize^6)
    */
    
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];
    }
    
/**
       判断(x1,y1)与(x2,y2)是否直接可到
    */
    
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 代码

/**
  注:: 对原题中
        "请你计算n个骑士的最早聚会地点和要走多少天.要求尽早聚会,且n个人走的总步数最少"
       感觉有歧义,不知道是"最早聚会"条件优先还是"走的总步数最少"条件优先.
       本代码中采用的是先考虑"最早聚会",其次考虑"走的总步数最少".另: 解未必唯一
**
  &#Together.cpp
  算法描叙:
      将棋盘上的SIZE*SIZE个位置看成SIZE*SIZE个节点,并且两个节点存在连线当且仅当马能够在这两个位置直接走动.
      定义两个节点m,n的距离dest[m][n]为马从m走到n所需的最少步数
      这样,可以通过Floyd-Warshall算法得到dest.
      算法的时间复杂度为O(SIZE^6),空间复杂度为O(SIZE^4)
      余略
   @author Eastsun
   @version 1.0 2007/9/3
*/
#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;

// 一个用于表示"无限大"的数,只要比棋盘上任意两点的距离都大就OK
const
 
int
 INFINITY = 2*SIZE*SIZE;

// dest[m][n] 表示棋盘上m点到n点的距离
// 其中 棋盘上坐标为(x,y)的点对应dest中 x+y*8 的点
int
 dest[SIZE*SIZE][SIZE*SIZE];

/**
   点m与点n在棋盘上是否直接可到
*/
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)
            );
}

/**
  计算dest的值
*/
void
 init(){

    
//初始化dest,将dest[n][n]设为0,可以直接到达的设为1,其余设为INFINITY
    
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;

    
//计算dest
    
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;
}

• Source.rar (2.8 KB)
• 描述: 本文中用到的代码
• 下载次数: 32

分享到：

Java SE 6 Update N Early Access is now a ... | 《程序员》2007第八期之算法擂台

• 2007-09-16 00:42
• 浏览 3181
• 评论(2)
• 论坛回复 / 浏览 (2 / 4084)
• 查看更多

评论

2 楼 Eastsun 2007-09-21  

呵呵,楼上的代码我之前看了
我也加入pipboy圈子了,有机会一起交流~

1 楼 leon_a 2007-09-21  

这个题我同学发到pipboy圈子里，我还现买了一本《程序员》拿来看（浪费我10块钱，也没发现有什么好文章，总是拿些概念来说事），题目本身就有问题。不过找两点最短路径，我是用bfs+记录的方式，再用上小暴力搜索解决的。看到你的程序，也给我一些新鲜思路，有空一起圈子里讨论