ITPub博客

首页 > Linux操作系统 > Linux操作系统 > 找跳马最短路径的算法

找跳马最短路径的算法

原创 Linux操作系统 作者:piliskys 时间:2006-02-22 00:00:00 0 删除 编辑
今天在网上看到一个{找跳马最短路径的算法} Find shortest way of a Chinese chess horse that jump from (0, 0) to (m, n) in a grid area of m*n, and output the step number and way points. For example, in a grid area of (3 * 2), a horse can jump as (0, 0)->(1, 2)->(2, 0)->(3,2). And step number is 3. 感觉在一个m*n的矩阵中跳要考虑边界问题,在此用java写了一下,没有考虑边界,以下程序只在无限二维中成立
代码如下

/**
 * 
@author : piliskys
 * Date: 2006-2-22
 * Time: 13:50:56
 * 找跳马最短路径的算法
 * 
 
*/

public class HorsePro {
    
public static void main(String[] arg) {
        HorsePosition start 
= new HorsePosition(00);
        HorsePosition end 
= new HorsePosition(0,1);
        
int index=0;
        
while (true{
               index
++;
            HorsePosition her 
= getNext(start, end);
            
if (her.positionX == 0 && her.positionY == 0||index==7)
                
break;
            start 
= new HorsePosition(start.positionX + her.positionX, start.positionY + her.positionY);
            System.out.println(
"第["+index+"]步=>"+start);
        }

    }

      
/**
       * 以下为构造一个位置类
       
*/

    
static class HorsePosition {
        HorsePosition(
int a, int b) {
            
this.positionX = a;
            
this.positionY = b;
        }

        
int positionX;
        
int positionY;
        
public String toString() {
            
return "[" + this.positionX + "," + this.positionY + "]";
        }

    }


    
public static HorsePosition getNext(HorsePosition a, HorsePosition b) {
        
int x, y, z;
        x 
= b.positionX - a.positionX;
        y 
= b.positionY - a.positionY;
        z 
= Math.abs(x) + Math.abs(y);
        
if (z >= 3{
            
if (Math.abs(x) > Math.abs(y)) {
                
int yy;
                
if (y == 0)  yy = 1;
                
else
                    yy 
= y / Math.abs(y);

                
return (new HorsePosition(2 * x / Math.abs(x), yy));

            }
 else
            
{
                
int xx;
                
if (x == 0)  xx = 1;
                
else
                    xx 
= x / Math.abs(x);
                
return (new HorsePosition(xx, 2 * y / Math.abs(y)));
            }

        }
 else
         
if (z == 2){

            
if(x==0){
                
return    new HorsePosition(2,y/2 );
            }

            
if(y==0){
                
return    new HorsePosition(x/2,1 );
            }

          
if(x*y!=0){
             
return    new HorsePosition(2*x,-y );
          }

         }

         
else if(z==1)//说明z==1的情况了
             if(x==0){
               
return     new HorsePosition(1,2*y );
             }

             
else
        
return     new HorsePosition(2*x,1 );
         }


      
//以下说明完成了
       return  new   HorsePosition(0,0 );

    }



}

来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/134308/viewspace-140581/,如需转载,请注明出处,否则将追究法律责任。

上一篇: ajax的继续学习
请登录后发表评论 登录
全部评论

注册时间:2008-01-14

  • 博文量
    68
  • 访问量
    160293