今天在网上看到一个{找跳马最短路径的算法} 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
: <a href="piliskys@163.com">piliskys</a>
* 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
);
}
}
