2007-09-16

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

关键字: 算法 程序员 算法擂台 骑士聚会 Floyd-Warshall

原题:在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 代码
  1. /**  
  2.    &#Main.java  
  3.    ＜程序员＞2007第九期算法擂台之JAVA代码  
  4.    注: 该问题的解未必唯一,但根据问题需要,只给出一个解  
  5.    另: 经测试,运行1000次new Knight()大约耗时6000毫秒  
  6.    @author Eastsun  
  7.    @version 1.0 2007/9/3  
  8. */  
  9. import java.util.Scanner;   
  10. public class Main{   
  11.     public static void main(String[] args){   
  12.         Scanner scan =new Scanner(System.in);   
  13.         int n =scan.nextInt();   
  14.         int[][] pos =new int[n][2];   
  15.         for(int index =0;index＜n;index ++){   
  16.             pos[index][0] =scan.nextInt();   
  17.             pos[index][1] =scan.nextInt();   
  18.         }   
  19.         ResultInf result =new Knight().solve(pos);   
  20.         System.out.print(result.x +" " +result.y +" " +result.days);   
  21.     }   
  22. }   
  23.   
  24. class Knight{   
  25.     private static final int DEFAULT_SIZE = 8;   
  26.        
  27.     private int boardSize;   
  28.        
  29.     //dis[i][j]表示骑士从棋盘上位置i到j所需的最少步数,其中位置i对于棋盘坐标(i%boardSize,i/boardSize)   
  30.     private int[][] dist;   
  31.     /**  
  32.        Knight的构造函数  
  33.        @param boardSize 棋盘的大小,默认值为8  
  34.     */  
  35.     public Knight(int boardSize){   
  36.         this.boardSize =boardSize;   
  37.         initDist();   
  38.     }   
  39.     public Knight(){   
  40.         this(DEFAULT_SIZE);   
  41.     }   
  42.     /**  
  43.        根据骑士的位置求解  
  44.        @param pos 一个int[][2]数组,第k个骑士的位置为(pos[k][0],pos[k][1])  
  45.        @return result 该问题的解,注意:当result.days ==Integer.MAX_VALUE的时候说明这些骑士永远不可能聚在一起  
  46.     */  
  47.     public ResultInf solve(int[][] pos){   
  48.         if(pos ==null||pos.length ==0|| pos[0].length !=2) throw new IllegalArgumentException();   
  49.         int location =0,days =Integer.MAX_VALUE,allDays =0;   
  50.         for(int n =0;n＜boardSize*boardSize;n ++){   
  51.             int max =0,sum =0;   
  52.             for(int index =0;index＜pos.length;index ++){   
  53.                 int dis = dist[n][pos[index][0]+pos[index][1]*boardSize];   
  54.                 sum += dis;   
  55.                 if(max＜dis) max =dis;   
  56.             }   
  57.             if(days＞max ||(days==max&&allDays＞sum)){   
  58.                 days =max;   
  59.                 allDays =sum;   
  60.                 location =n;   
  61.             }   
  62.         }   
  63.         return new ResultInf(location%boardSize,location/boardSize,days);   
  64.     }   
  65.     /**  
  66.        使用Floyd-Warshall算法计算dist的值,时间复杂度O(boardSize^6)  
  67.     */  
  68.     private void initDist(){   
  69.         int count =boardSize*boardSize;   
  70.         dist =new int[count][count];   
  71.         for(int n =0;n＜count;n++)   
  72.             for(int m =0;m＜count;m++)   
  73.                 if(m!=n) dist[m][n] = isConnect(m%boardSize,m/boardSize,n%boardSize,n/boardSize)? 1: Integer.MAX_VALUE;   
  74.                    
  75.         for(int k =0;k＜count;k++)   
  76.             for(int n =0;n＜count;n++)   
  77.                 for(int m =0;m＜count;m++)   
  78.                     if(dist[n][k]＜Integer.MAX_VALUE&&dist[k][m]＜Integer.MAX_VALUE&&   
  79.                           dist[n][k]+dist[k][m] ＜dist[n][m])   
  80.                               dist[n][m] =dist[n][k] +dist[k][m];   
  81.     }   
  82.     /**  
  83.        判断(x1,y1)与(x2,y2)是否直接可到  
  84.     */  
  85.     private boolean isConnect(int x1,int y1,int x2,int y2){   
  86.         return (x1!=x2&&y1!=y2&&Math.abs(x1-x2)+Math.abs(y1-y2)==3);   
  87.     }   
  88. }   
  89.   
  90. /**  
  91.    一个用于保存求解信息的类  
  92. */  
  93. class ResultInf{   
  94.     public int x,y,days;   
  95.     public ResultInf(int x,int y,int days){   
  96.         this.x =x;   
  97.         this.y =y;   
  98.         this.days =days;   
  99.     }   
  100. }  

 

 

这个是C++版:

cpp 代码
  1. /**  
  2.   注:: 对原题中  
  3.         "请你计算n个骑士的最早聚会地点和要走多少天.要求尽早聚会,且n个人走的总步数最少"  
  4.        感觉有歧义,不知道是"最早聚会"条件优先还是"走的总步数最少"条件优先.  
  5.        本代码中采用的是先考虑"最早聚会",其次考虑"走的总步数最少".另: 解未必唯一  
  6. **  
  7.   &#Together.cpp  
  8.   算法描叙:  
  9.       将棋盘上的SIZE*SIZE个位置看成SIZE*SIZE个节点,并且两个节点存在连线当且仅当马能够在这两个位置直接走动.  
  10.       定义两个节点m,n的距离dest[m][n]为马从m走到n所需的最少步数  
  11.       这样,可以通过Floyd-Warshall算法得到dest.  
  12.       算法的时间复杂度为O(SIZE^6),空间复杂度为O(SIZE^4)  
  13.       余略  
  14.    @author Eastsun  
  15.    @version 1.0 2007/9/3  
  16. */  
  17. #include＜iostream＞   
  18. #define X(n) ((n)&7)   
  19. #define Y(n) ((n)＞＞3)   
  20. #define P(x,y) ((x)+((y)＜＜3))   
  21. #define ABS(x) ((x)＞=0?(x):-(x))   
  22.   
  23. // 棋盘的大小   
  24. const int SIZE = 8;   
  25.   
  26. // 一个用于表示"无限大"的数,只要比棋盘上任意两点的距离都大就OK   
  27. const int INFINITY = 2*SIZE*SIZE;   
  28.   
  29. // dest[m][n] 表示棋盘上m点到n点的距离   
  30. // 其中 棋盘上坐标为(x,y)的点对应dest中 x+y*8 的点   
  31. int dest[SIZE*SIZE][SIZE*SIZE];   
  32.   
  33. /**  
  34.    点m与点n在棋盘上是否直接可到  
  35. */  
  36. bool connected(int m,int n){   
  37.     int x1 =X(m), y1 =Y(m);   
  38.     int x2 =X(n), y2 =Y(n);   
  39.     return ( (ABS(x1-x2)==2&&ABS(y1-y2)==1)||   
  40.              (ABS(x1-x2)==1&&ABS(y1-y2)==2)    
  41.             );   
  42. }   
  43.   
  44. /**  
  45.   计算dest的值  
  46. */  
  47. void init(){   
  48.        
  49.     //初始化dest,将dest[n][n]设为0,可以直接到达的设为1,其余设为INFINITY   
  50.     for(int m =0;m＜ SIZE*SIZE; m++)   
  51.         for(int n =0;n＜ SIZE*SIZE; n++)   
  52.             if(m == n)   dest[m][n] = 0;   
  53.             else         dest[m][n] = connected(m,n)? 1: INFINITY;   
  54.                    
  55.     //计算dest   
  56.     for(int k=0;k＜ SIZE*SIZE; k++)   
  57.         for(int m=0;m＜ SIZE*SIZE; m++)   
  58.             for(int n=0;n＜ SIZE*SIZE; n++)   
  59.                 if(dest[m][n] ＞dest[m][k]+dest[k][n])   
  60.                     dest[m][n] =dest[m][k]+dest[k][n];   
  61. }   
  62.   
  63. int main(){   
  64.     init();   
  65.     int size;   
  66.     std::cin＞＞size;   
  67.     int *pos =new int[size];   
  68.     for(int i =0;i＜size;i++){   
  69.         int x,y;   
  70.         std::cin＞＞x＞＞y;   
  71.         pos[i] =P(x,y);   
  72.     }   
  73.     int days =INFINITY,allDays,location;   
  74.     for(int m =0;m＜SIZE*SIZE;m++){   
  75.         int max =0,sum =0;   
  76.         for(int k =0;k＜size;k++){   
  77.             sum += dest[m][pos[k]];   
  78.             if(dest[m][pos[k]] ＞max) max =dest[m][pos[k]];   
  79.         }   
  80.         if(max＜days ||(max ==days&&sum＜allDays) ){   
  81.             days =max;   
  82.             allDays =sum;   
  83.             location   =m;   
  84.         }   
  85.     }   
  86.     delete[] pos;   
  87.     std::cout＜＜X(location)＜＜" "＜＜Y(location)＜＜" "＜＜days;   
  88.     return 0;   
  89. }   
  • Source.rar (2.8 KB)
  • 描述: 本文中用到的代码
  • 下载次数: 24
评论
Eastsun 2007-09-21
呵呵,楼上的代码我之前看了
我也加入pipboy圈子了,有机会一起交流~
leon_a 2007-09-21
这个题我同学发到pipboy圈子里，我还现买了一本《程序员》拿来看（浪费我10块钱，也没发现有什么好文章，总是拿些概念来说事），题目本身就有问题。不过找两点最短路径，我是用bfs+记录的方式，再用上小暴力搜索解决的。看到你的程序，也给我一些新鲜思路，有空一起圈子里讨论
发表评论

提醒: 该博客已发表在公共论坛，博客所有留言会成为论坛回贴，留言请注意遵守论坛发贴规则

您还没有登录，请登录后发表评论

Eastsun
搜索本博客
我的相册
1b680e5a-efae-3ec3-8ccd-970a4a72a056-thumb
6.5beta.PNG
共 61 张
最近加入圈子
存档
最新评论