piliskys

今天在網(wǎng)上看到一個{找跳馬最短路徑的算法} 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);
????????}
????}
?????? /**?*/ /** ? */ /**?*/ /**
???????*?以下為構(gòu)造一個位置類
??????? */
???? 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 ?);

????}


}