今天在网上看到一个{找跳马最短路径的算法} 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(0, 0);
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 );
}
}
代码如下
/** *//** * @author : * Date: 2006-2-22 * Time: 13:50:56 * 找跳马最短路径的算法 * public class HorsePro { public static void main(String[] arg) { HorsePosition start = new HorsePosition(0, 0); 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博客 ” ，链接：https://blog.itpub.net/134308/viewspace-140581/ ，如需转载，请注明出处，否则将追究法律责任。
上一篇：
ajax的继续学习
请登录后发表评论
登录
全部评论
