私は次のプログラミングコンテストのために練習してきましたが、私は完全に当惑している質問に出くわしました。しかし、それは決して思い浮かばないということで、指を交差させるのではなく、今学ぶべき概念だと感じています。
基本的には、チェス盤の騎士の駒を扱います。開始位置と終了位置の2つの入力が与えられます。次に、目標の場所に到達するために騎士がたどることができる最短経路を計算して印刷することが目標です。
私は最短経路のようなものを扱ったことがなく、どこから始めればよいのかさえわかりません。これに取り組むために私はどのような論理を採用していますか？
PS関連性がある場合は、騎士の通常の動きを補うために、騎士が行うことができる（潜在的に）8つの動きによって形成される正方形の四隅に移動できるようにする必要があります。騎士の場所。
編集： 彼がここに提示された式を修正したサイモンの答えを参照してください。
実際にはO（1）式があります
これは私がそれを視覚化するために作成した画像です（騎士がN番目の動きで到達できる正方形は同じ色で描かれています）。
ここでパターンに気付くことができますか？
パターンはわかりますが、正方形から正方形に移動するのに必要な移動回数を返す関数を見つけるのは非常に困難ですf( x , y )。( 0 , 0 )( x , y )
しかし、これが次の場合に機能する式です0 <= y <= x
int f( int x , int y )
{
int delta = x - y;
if( y > delta )
return 2 * ( ( y - delta ) / 3 ) + delta;
else
return delta - 2 * ( ( delta - y ) / 4 );
}
注：この質問はSACO2007の1日目
に行われました。
解決策はこちらです
これが正しいO（1）ソリューションですが、騎士がチェスの騎士のようにのみ移動し、無限のチェス盤上を移動する場合は次のようになります。
https://jsfiddle.net/graemian/5qgvr1ba/11/
これを見つけるための鍵は、ボードを描くときに現れるパターンに気づくことです。下の図では、正方形の数字は、その正方形に到達するために必要な最小移動数です（幅優先探索を使用してこれを見つけることができます）。
解は軸と対角線にわたって対称であるため、x>=0およびy>=xの場合のみを描画しました。
左下のブロックが開始位置であり、ブロック内の数字は、それらのブロックに到達するための最小移動数を表します。
注意すべき3つのパターンがあります。
（両方の対角線のセットが左上から右下に表示されていることを確認してください。移動回数は一定です。左下の右上の対角線ははるかに複雑です。）
それぞれの式を導き出すことができます。黄色のブロックは特殊なケースです。したがって、解決策は次のようになります。
function getMoveCountO1(x, y) {
var newXY = simplifyBySymmetry(x, y);
x = newXY.x;
y = newXY.y;
var specialMoveCount = getSpecialCaseMoveCount(x ,y);
if (specialMoveCount !== undefined)
return specialMoveCount;
else if (isVerticalCase(x, y))
return getVerticalCaseMoveCount(x ,y);
else if (isPrimaryDiagonalCase(x, y))
return getPrimaryDiagonalCaseMoveCount(x ,y);
else if (isSecondaryDiagonalCase(x, y))
return getSecondaryDiagonalCaseMoveCount(x ,y);
}
最も難しいのは垂直グループです。
function isVerticalCase(x, y) {
return y >= 2 * x;
}
function getVerticalCaseMoveCount(x, y) {
var normalizedHeight = getNormalizedHeightForVerticalGroupCase(x, y);
var groupIndex = Math.floor( normalizedHeight / 4);
var groupStartMoveCount = groupIndex * 2 + x;
return groupStartMoveCount + getIndexInVerticalGroup(x, y);
}
function getIndexInVerticalGroup(x, y) {
return getNormalizedHeightForVerticalGroupCase(x, y) % 4;
}
function getYOffsetForVerticalGroupCase(x) {
return x * 2;
}
function getNormalizedHeightForVerticalGroupCase(x, y) {
return y - getYOffsetForVerticalGroupCase(x);
}
他の場合についてはフィドルを参照してください。
多分私が逃したより単純なまたはよりエレガントなパターンがありますか？もしそうなら、私はそれらを見たいです。特に、青い縦の場合にいくつかの斜めのパターンに気づきましたが、私はそれらを調査していません。それでも、このソリューションはO（1）制約を満たしています。
ここにグラフがあり、使用可能なすべての移動が接続され（value = 1）、使用できない移動が切断されています（value = 0）、スパース行列は次のようになります。
(a1,b3)=1,
(a1,c2)=1,
.....
また、グラフ内の2点の最短経路は、 http：//en.wikipedia.org/wiki/Dijkstra's_algorithmを使用して見つけることができます。
ウィキペディアページからの擬似コード：
function Dijkstra(Graph, source):
for each vertex v in Graph: // Initializations
dist[v] := infinity // Unknown distance function from source to v
previous[v] := undefined // Previous node in optimal path from source
dist[source] := 0 // Distance from source to source
Q := the set of all nodes in Graph
// All nodes in the graph are unoptimized - thus are in Q
while Q is not empty: // The main loop
u := vertex in Q with smallest dist[]
if dist[u] = infinity:
break // all remaining vertices are inaccessible from source
remove u from Q
for each neighbor v of u: // where v has not yet been removed from Q.
alt := dist[u] + dist_between(u, v)
if alt < dist[v]: // Relax (u,v,a)
dist[v] := alt
previous[v] := u
return dist[]
編集：
Introduction to AlgorithmsISBN0-262-03384-4を読むことです。または、ウィキペディア、 http：//en.wikipedia.org/wiki/List_of_algorithmsを試すことができます私が最近遭遇した非常に興味深い問題。いくつかの解決策を探した後、 SACO 2007 Day 1の解決策O(1) time and space complexityで与えられた分析式（）を復元しようとしました。
まず第一に、数式を修正するのに役立った非常に優れた視覚化を提供してくれたGraemePyleに感謝したいと思います。
何らかの理由で（おそらく単純化または美しさ、あるいは単なる間違いのために）、彼らはminusサインをfloorオペレーターに移しました。その結果、彼らは間違った式を持っていfloor(-a) != -floor(a) for any aます。
正しい分析式は次のとおりです。
var delta = x-y;
if (y > delta) {
return delta - 2*Math.floor((delta-y)/3);
} else {
return delta - 2*Math.floor((delta-y)/4);
}
この式は、（1,0）と（2,2）のコーナーケースを除いて、すべての（x、y）ペア（軸と対角対称を適用した後）で機能します。これらはパターンに適合せず、次のスニペットにハードコードされています。
function distance(x,y){
// axes symmetry
x = Math.abs(x);
y = Math.abs(y);
// diagonal symmetry
if (x < y) {
t = x;x = y; y = t;
}
// 2 corner cases
if(x==1 && y == 0){
return 3;
}
if(x==2 && y == 2){
return 4;
}
// main formula
var delta = x-y;
if(y>delta){
return delta - 2*Math.floor((delta-y)/3);
}
else{
return delta - 2*Math.floor((delta-y)/4);
}
}
$body = $("body");
var html = "";
for (var y = 20; y >= 0; y--){
html += '<tr>';
for (var x = 0; x <= 20; x++){
html += '<td style="width:20px; border: 1px solid #cecece" id="'+x+'_'+y+'">'+distance(x,y)+'</td>';
}
html += '</tr>';
}
html = '<table>'+html+'</table>';
$body.append(html);<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>注：jQueryは説明のみに使用されます。コードについては、distance関数を参照してください。
はい、ダイクストラとBFSで答えが得られますが、この問題のチェスコンテキストは、特に無限チェス盤で、一般的な最短経路アルゴリズムよりもはるかに高速なソリューションを生み出すことができる知識を提供すると思います。
簡単にするために、チェス盤を（x、y）平面として説明しましょう。目標は、候補ステップ（+-1、+-2）、（+-2、+-1）、および（+-2）のみを使用して、（x0、y0）から（x1、y1）への最短経路を見つけることです。 、+-2）、質問のPSで説明されているように
新しい観察結果は次のとおりです。角のある正方形を描く（x-4、y-4）、（x-4、y + 4）、（x + 4、y-4）、（x + 4、y + 4） 。このセット（S4と呼びます）には32ポイントが含まれています。これらの32ポイントのいずれかから（x、y）への最短経路には、正確に2回の移動が必要です。
セットS3（同様に定義）の24ポイントのいずれかから（x、y）への最短経路には、少なくとも2回の移動が必要です。
したがって、| x1-x0|>4または|y1-y0|> 4の場合、（x0、y0）から（x1、y1）への最短経路は（x0、y0）から（x0、y0）への最短経路よりも正確に2移動大きくなります。 S4。そして後者の問題は、簡単な反復ですばやく解決できます。
N = max（| x1-x0 |、| y1-y0 |）とします。N> = 4の場合、（x0、y0）から（x1、y1）への最短経路にはceil（N / 2）ステップがあります。
上記のO（1）の回答[ https://stackoverflow.com/a/8778592/4288232byMustafaSerdarŞanlı ]は実際には機能していません。（（1,0）または（2,2）の明らかなエッジケースは別として、（1,1）または（3,2）または（4,4）をチェックしてください）。
以下は、（「テスト」を追加して）機能するはるかに醜いソリューション（python）です。
def solve(x,y):
x = abs(x)
y = abs(y)
if y > x:
temp=y
y=x
x=temp
if (x==2 and y==2):
return 4
if (x==1 and y==0):
return 3
if(y == 0 or float(y) / float(x) <= 0.5):
xClass = x % 4
if (xClass == 0):
initX = x/2
elif(xClass == 1):
initX = 1 + (x/2)
elif(xClass == 2):
initX = 1 + (x/2)
else:
initX = 1 + ((x+1)/2)
if (xClass > 1):
return initX - (y%2)
else:
return initX + (y%2)
else:
diagonal = x - ((x-y)/2)
if((x-y)%2 == 0):
if (diagonal % 3 == 0):
return (diagonal/3)*2
if (diagonal % 3 == 1):
return ((diagonal/3)*2)+2
else:
return ((diagonal/3)*2)+2
else:
return ((diagonal/3)*2)+1
def test():
real=[
[0,3,2,3,2,3,4,5,4,5,6,7,6,7],
[3,2,1,2,3,4,3,4,5,6,5,6,7,8],
[2,1,4,3,2,3,4,5,4,5,6,7,6,7],
[3,2,3,2,3,4,3,4,5,6,5,6,7,8],
[2,3,2,3,4,3,4,5,4,5,6,7,6,7],
[3,4,3,4,3,4,5,4,5,6,5,6,7,8],
[4,3,4,3,4,5,4,5,6,5,6,7,6,7],
[5,4,5,4,5,4,5,6,5,6,7,6,7,8],
[4,5,4,5,4,5,6,5,6,7,6,7,8,7],
[5,6,5,6,5,6,5,6,7,6,7,8,7,8],
[6,5,6,5,6,5,6,7,6,7,8,7,8,9],
[7,6,7,6,7,6,7,6,7,8,7,8,9,8]]
for x in range(12):
for y in range(12):
res = solve(x,y)
if res!= real[x][y]:
print (x, y), "failed, and returned", res, "rather than", real[x][y]
else:
print (x, y), "worked. Cool!"
test()
あなたがする必要があるのは、騎士の可能な動きをグラフとして考えることです。ここで、ボード上のすべての位置はノードであり、可能な動きはエッジとして他の位置に移動します。すべてのエッジの重みまたは距離が同じであるため、ダイクストラのアルゴリズムは必要ありません（これらはすべて同じように簡単または短いです）。開始点から終了位置に到達するまで、BFS検索を実行できます。
Codilityテストでこの問題に最初に遭遇しました。彼らは私にそれを解決するために30分を与えました-この結果に到達するのにそれよりもかなり長い時間がかかりました！問題は、騎士が合法的な騎士の動きだけを使用して0,0からx、yに移動するのに何回の動きが必要かということでした。xとyは多かれ少なかれ無制限でした（したがって、ここでは単純な8x8チェス盤について話していません）。
彼らはO（1）ソリューションを望んでいました。プログラムが問題を明確に解決しているソリューションが必要でした（つまり、Graemeのパターンよりも明らかに正しいものが必要でした-パターンには、見ない場所で分解する習慣があります）。 Mustafaのソリューションのように、議論の余地のない式
だから、これが私の解決策です、それが価値があるもののために。他の人がそうであるように、解が軸と対角線に関して対称であることに注意することから始めます。したがって、0> = y>=xについてのみ解く必要があります。説明（およびコード）を簡単にするために、問題を逆にします。騎士はx、yで始まり、0,0を目指しています。
問題を原点の近くまで縮小するとします。やがて「vicinty」が実際に何を意味するかについて説明しますが、今のところ、いくつかの解決策を虎の巻（左下の原点）に書き留めておきましょう。
2 1 4 3
3 2 1 2
0 3 2 3
したがって、グリッド上のx、yが与えられると、原点への移動の数を読み取ることができます。
グリッドの外から始めた場合は、グリッドに戻る必要があります。y = x/2で表される線である「正中線」を紹介します。その線上のx、yにいる騎士は、一連の8時の動き（つまり、（-2、-1）の動き）を使用して虎の巻に戻ることができます。x、yが正中線より上にある場合は、8時と7時の連続移動が必要であり、正中線より下にある場合は、8時と10時の連続が必要です。 '時計が動きます。ここで注意すべき2つのこと：
それでは、上記の正中線の動きを見てみましょう。私たちが主張しているのは、次のとおりです。
（dx; dy）=（2,1; 1,2）（n8; n7）（行列表記、数学タイプ設定なし-列ベクトル（dx; dy）は、正方行列に列ベクトル（n8; n7）を掛けたものに等しい- 8時の移動数と7時の移動数）、および同様に;
（dx; dy）=（2,2; 1、-1）（n8; n10）
私は、dx、dyがおおよそ（x、y）になると主張しているので、（x-dx、y-dy）は原点の近くにあります（「近く」が何であれ）。
これらの用語を計算するコードの2行はこれらの解決策ですが、いくつかの有用なプロパティを持つように選択されています。
（これらの証拠が必要ですか？）したがって、騎士の距離はn7、n8、n10と虎の巻[x-dx、y-dy]の合計になり、虎の巻は次のようになります。
. . 4
. 2 .
0 3 2
さて、これで話は終わりではありません。下の行の3を見てください。これに到達できる唯一の方法は次のいずれかです。
右上の4でも同様の最適化が行われます。そこから出発する以外に、そこに到達する唯一の方法は、（4,3）から8時の位置に移動することです。これはチートシートにはありませんが、そこにある場合、距離は3になります。これは、代わりに（3,1）に7時を刻むことができ、距離が2しかないためです。したがって、1つをバックトラックする必要があります。 8時移動してから、7時先に進みます。
したがって、虎の巻にもう1つ番号を追加する必要があります。
. . 4
. 2 . 2
0 3 2
（注：（0,1）と（0,2）からのバックトラッキングの最適化はたくさんありますが、ソルバーが私たちをそこに連れて行くことは決してないので、それらについて心配する必要はありません。）
それで、ここにこれを評価するためのいくつかのPythonコードがあります：
def knightDistance (x, y):
# normalise the coordinates
x, y = abs(x), abs(y)
if (x<y): x, y = y, x
# now 0 <= y <= x
# n8 means (-2,-1) (8 o'clock), n7 means (-1,-2) (7 o'clock), n10 means (-2,+1) (10 o'clock)
if (x>2*y):
# we're below the midline. Using 8- & 10-o'clock moves
n7, n8, n10 = 0, (x + 2*y)//4, (x - 2*y + 1)//4
else:
# we're above the midline. Using 7- and 8-o'clock moves
n7, n8, n10 = (2*y - x)//3, (2*x - y)//3, 0
x -= 2*n8 + n7 + 2*n10
y -= n8 + 2*n7 - n10
# now 0<=x<=2, and y <= x. Also (x,y) != (2,1)
# Try to optimise the paths.
if (x, y)==(1, 0): # hit the 3. Did we need to?
if (n8>0): # could have passed through the 2 at 3,1. Back-up
x, y = 3, 1; n8-=1;
if (x, y)==(2, 2): # hit the 4. Did we need to?
if (n8>0): # could have passed through a 3 at 4,3. Back-up, and take 7 o'clock to 2 at 3,1
x, y = 3, 1; n8-=1; n7+=1
# Almost there. Now look up the final leg
cheatsheet = [[0, 3, 2], [2, None, 2], [4]]
return n7 + n8 + n10 + cheatsheet [y][x-y]
ちなみに、実際のルートを知りたい場合は、このアルゴリズムもそれを提供します。これは、n7の7時の動きの連続であり、その後にn8の8時の動きが続く（または散在する）、n1010です。時計が移動し、虎の巻（それ自体が虎の巻に含まれている可能性があります）によって指示されたダンスがあります。
今：これが正しいことを証明する方法。問題自体には限りがないため、これらの結果を正解の表と比較するだけでは不十分です。しかし、正方形sの騎士の距離がdである場合、{m}がsからの合法的な移動のセットである場合、（s + m）の騎士の距離はd-1またはd+1のいずれかでなければなりません。すべてのmのために。（これを証明する必要がありますか？）さらに、sが原点でない限り、距離がd-1であるそのような正方形が少なくとも1つ存在する必要があります。したがって、このプロパティがすべての正方形に当てはまることを示すことで、正当性を証明できます。したがって：
def validate (n):
def isSquareReasonable (x, y):
d, downhills = knightDistance (x, y), 0
moves = [(1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, -1), (-2, 1), (-1, 2)]
for dx, dy in moves:
dd = knightDistance (x+dx, y+dy)
if (dd == d+1): pass
elif (dd== d-1): downhills += 1
else: return False;
return (downhills>0) or (d==0)
for x in range (0, n+1):
for y in range (0, n+1):
if not isSquareReasonable (x, y): raise RuntimeError ("Validation failed")
または、下り坂から原点までのルートを追跡することで、任意の1つの正方形の正しさを証明できます。まず、上記のようにsの妥当性を確認してから、距離（s + m）==d-1となるようなs+mを選択します。原点に到達するまで繰り返します。
ハウザット？
/*
This program takes two sets of cordinates on a 8*8 chessboard, representing the
starting and ending points of a knight's path.
The problem is to print the cordinates that the knight traverses in between, following
the shortest path it can take.
Normally this program is to be implemented using the Djikstra's algorithm(using graphs)
but can also be implemented using the array method.
NOTE:Between 2 points there may be more than one shortest path. This program prints
only one of them.
*/
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
int m1=0,m2=0;
/*
This array contains three columns and 37 rows:
The rows signify the possible coordinate differences.
The columns 1 and 2 contains the possible permutations of the row and column difference
between two positions on a chess board;
The column 3 contains the minimum number of steps involved in traversing the knight's
path with the given permutation*/
int arr[37][3]={{0,0,0},{0,1,3},{0,2,2},{0,3,3},{0,4,2},{0,5,3},{0,6,4},{0,7,5}, {1,1,2},{1,2,1},{1,3,2},{1,4,3},{1,5,4},{1,6,3},{1,7,4},{2,2,4},{2,3,3},{2,4,2},
{2,5,3},{2,6,3},{2,7,5},{3,3,2},{3,4,3},{3,5,4},{3,6,3},{3,7,4},{4,4,4},{4,5,3},{4,6,4},{4,7,5},{5,5,4},{5,6,5},{5,7,4},{6,6,5},{6,7,5},{7,7,6}};
void printMoves(int,int,int,int,int,int);
void futrLegalMove(int,int,int,int);
main()
{
printf("KNIGHT'S SHORTEST PATH ON A 8*8 CHESSBOARD :\n");
printf("------------------------------------------");
printf("\nThe chessboard may be treated as a 8*8 array here i.e. the (1,1) ");
printf("\non chessboard is to be referred as (0,0) here and same for (8,8) ");
printf("\nwhich is to be referred as (7,7) and likewise.\n");
int ix,iy,fx,fy;
printf("\nEnter the initial position of the knight :\n");
scanf("%d%d",&ix,&iy);
printf("\nEnter the final position to be reached :\n");
scanf("%d%d",&fx,&fy);
int px=ix,py=iy;
int temp;
int tx,ty;
printf("\nThe Knight's shortest path is given by :\n\n");
printf("(%d, %d)",ix,iy);
futrLegalMove(px,py,m1,m2);
printMoves(px,py,fx,fy,m1,m2);
getch();
}
/*
This method checkSteps() checks the minimum number of steps involved from current
position(a & b) to final position(c & d) by looking up in the array arr[][].
*/
int checkSteps(int a,int b,int c,int d)
{
int xdiff, ydiff;
int i, j;
if(c>a)
xdiff=c-a;
else
xdiff=a-c;
if(d>b)
ydiff=d-b;
else
ydiff=b-d;
for(i=0;i<37;i++)
{
if(((xdiff==arr[i][0])&&(ydiff==arr[i][1])) || ((xdiff==arr[i][1])&& (ydiff==arr[i] [0])))
{
j=arr[i][2];break;
}
}
return j;
}
/*
This method printMoves() prints all the moves involved.
*/
void printMoves(int px,int py, int fx, int fy,int a,int b)
{
int temp;
int tx,ty;
int t1,t2;
while(!((px==fx) && (py==fy)))
{
printf(" --> ");
temp=checkSteps(px+a,py+b,fx,fy);
tx=px+a;
ty=py+b;
if(!(a==2 && b==1))
{if((checkSteps(px+2,py+1,fx,fy)<temp) && checkMove(px+2,py+1))
{temp=checkSteps(px+2,py+1,fx,fy);
tx=px+2;ty=py+1;}}
if(!(a==2 && b==-1))
{if((checkSteps(px+2,py-1,fx,fy)<temp) && checkMove(px+2,py-1))
{temp=checkSteps(px+2,py-1,fx,fy);
tx=px+2;ty=py-1;}}
if(!(a==-2 && b==1))
{if((checkSteps(px-2,py+1,fx,fy)<temp) && checkMove(px-2,py+1))
{temp=checkSteps(px-2,py+1,fx,fy);
tx=px-2;ty=py+1;}}
if(!(a==-2 && b==-1))
{if((checkSteps(px-2,py-1,fx,fy)<temp) && checkMove(px-2,py-1))
{temp=checkSteps(px-2,py-1,fx,fy);
tx=px-2;ty=py-1;}}
if(!(a==1 && b==2))
{if((checkSteps(px+1,py+2,fx,fy)<temp) && checkMove(px+1,py+2))
{temp=checkSteps(px+1,py+2,fx,fy);
tx=px+1;ty=py+2;}}
if(!(a==1 && b==-2))
{if((checkSteps(px+1,py-2,fx,fy)<temp) && checkMove(px+1,py-2))
{temp=checkSteps(px+1,py-2,fx,fy);
tx=px+1;ty=py-2;}}
if(!(a==-1 && b==2))
{if((checkSteps(px-1,py+2,fx,fy)<temp) && checkMove(px-1,py+2))
{temp=checkSteps(px-1,py+2,fx,fy);
tx=px-1;ty=py+2;}}
if(!(a==-1 && b==-2))
{if((checkSteps(px-1,py-2,fx,fy)<temp) && checkMove(px-1,py-2))
{temp=checkSteps(px-1,py-2,fx,fy);
tx=px-1;ty=py-2;}}
t1=tx-px;//the step taken in the current move in the x direction.
t2=ty-py;//" " " " " " " " " " " " " " " " " " " " " y " " " " ".
px=tx;
py=ty;
printf("(%d, %d)",px,py);
futrLegalMove(px,py,t1,t2);
a=m1;
b=m2;
}
}
/*
The method checkMove() checks whether the move in consideration is beyond the scope of
board or not.
*/
int checkMove(int a, int b)
{
if(a>7 || b>7 || a<0 || b<0)
return 0;
else
return 1;
}
/*Out of the 8 possible moves, this function futrLegalMove() sets the valid move by
applying the following constraints
1. The next move should not be beyond the scope of the board.
2. The next move should not be the exact opposite of the previous move.
The 1st constraint is checked by sending all possible moves to the checkMove()
method;
The 2nd constraint is checked by passing as parameters(i.e. a and b) the steps of the
previous move and checking whether or not it is the exact opposite of the current move.
*/
void futrLegalMove(int px,int py,int a,int b)
{
if(checkMove(px+2,py+1) && (a!=-2 && b!=-1))
m1=2,m2=1;
else
{
if(checkMove(px+2,py-1)&& (a!=-2 && b!=1))
m1=2,m2=-1;
else
{
if(checkMove(px-2,py+1)&& (a!=2 && b!=-1))
m1=-2,m2=1;
else
{
if(checkMove(px-2,py-1)&& (a!=2 && b!=1))
m1=-2,m2=-1;
else
{
if(checkMove(px+1,py+2)&& (b!=-2 && a!=-1))
m2=2,m1=1;
else
{
if(checkMove(px+1,py-2)&& (a!=-1 && b!=2))
m2=-2,m1=1;
else
{
if(checkMove(px-1,py+2)&& (a!=1 && b!=-2))
m2=2,m1=-1;
else
{
if(checkMove(px-1,py-2)&& (a!=1 && b!=2))
m2=-2,m1=-1;
}}}}}}}
}
//End of Program.
私はまだグラフを研究していません。単純な配列を介してグラフを実装するという問題により、これ以外の解決策を導き出すことはできませんでした。位置をランクやファイル（通常のチェス表記）ではなく、配列インデックスとして扱いました。参考までに、これは8*8チェス盤専用です。改善のアドバイスはいつでも歓迎します。
*ロジックを理解するにはコメントで十分です。ただし、いつでも質問することができます。
* DEV-C ++ 4.9.9.2コンパイラ（Bloodshed Software）でチェック。
これもあなたを助けるかもしれないと思います。
NumWays(x,y)=1+min(NumWays(x+-2,y-+1),NumWays(x+-1,y+-2));
動的計画法を使用してソリューションを取得します。
PS：グラフのノードとエッジを宣言する手間をかけずに、BFSを使用します。
Perlで実装されたこの特定の問題の解決策は次のとおりです。最短経路の1つが表示されます。場合によっては、複数の経路が存在する可能性があります。
上記のアルゴリズムは使用しませんでしたが、他のソリューションと比較すると便利です。
#!/usr/local/bin/perl -w
use strict;
my $from = [0,0];
my $to = [7,7];
my $f_from = flat($from);
my $f_to = flat($to);
my $max_x = 7;
my $max_y = 7;
my @moves = ([-1,2],[1,2],[2,1],[2,-1],[1,-2],[-1,-2],[-2,-1],[-2,1]);
my %squares = ();
my $i = 0;
my $min = -1;
my @s = ( $from );
while ( @s ) {
my @n = ();
$i++;
foreach my $s ( @s ) {
unless ( $squares{ flat($s) } ) {
my @m = moves( $s );
push @n, @m;
$squares{ flat($s) } = { i=>$i, n=>{ map {flat($_)=>1} @m }, };
$min = $i if $squares{ flat($s) }->{n}->{$f_to};
}
}
last if $min > -1;
@s = @n;
}
show_path( $f_to, $min );
sub show_path {
my ($s,$i) = @_;
return if $s eq $f_from;
print "$i => $f_to\n" if $i == $min;
foreach my $k ( keys %squares ) {
if ( $squares{$k}->{i} == $i && $squares{$k}->{n}->{$s} ) {
$i--;
print "$i => $k\n";
show_path( $k, $i );
last;
}
}
}
sub flat { "$_[0]->[0],$_[0]->[1]" }
sub moves {
my $c = shift;
my @s = ();
foreach my $m ( @moves ) {
my $x = $c->[0] + $m->[0];
my $y = $c->[1] + $m->[1];
if ( $x >= 0 && $x <=$max_x && $y >=0 && $y <=$max_y) {
push @s, [$x, $y];
}
}
return @s;
}
__END__
public class Horse {
private int[][] board;
private int[] xer = { 2, 1, -1, -2, -2, -1, 1, 2 };
private int[] yer = { 1, 2, 2, 1, -1, -2, -2, -1 };
private final static int A_BIG_NUMBER = 10000;
private final static int UPPER_BOUND = 64;
public Horse() {
board = new int[8][8];
}
private int solution(int x, int y, int destx, int desty, int move) {
if(move == UPPER_BOUND) {
/* lets put an upper bound to avoid stack overflow */
return A_BIG_NUMBER;
}
if(x == 6 && y ==5) {
board[6][5] = 1;
return 1;
}
int min = A_BIG_NUMBER;
for (int i = 0 ; i < xer.length; i++) {
if (isMoveGood(x + xer[i], y + yer[i])) {
if(board[x + xer[i]][y + yer[i]] != 0) {
min = Integer.min(min, 1 + board[x +xer[i]] [y +yer[i]]);
} else {
min = Integer.min(min, 1 + solution(x + xer[i], y + yer[i], destx, desty, move + 1));
}
}
}
board[x][y] = min;
return min;
}
private boolean isMoveGood(int x, int y) {
if (x >= 0 && x < board.length && y >= 0 && y < board.length)
return true;
return false;
}
public static void main(String[] args) {
int destX = 6;
int destY = 7;
final Horse h = new Horse();
System.out.println(h.solution(0, 0, destX, destY, 0));
}
}
上記のGraemePyleの回答のjsfiddleからのrubyコードだけで、余分なコードをすべてストライプ化し、残りをrubyに変換して、彼のアルゴリズムによる解決策を得たようです。まだテスト中：
def getBoardOffset(board)
return board.length / 2
end
def setMoveCount(x, y, count, board)
offset = getBoardOffset(board)
board[y + offset][x + offset] = count
end
def getMoveCount(x, y, board)
offset = getBoardOffset(board)
row = board[y + offset]
return row[x + offset]
end
def isBottomOfVerticalCase(x, y)
return (y - 2 * x) % 4 == 0
end
def isPrimaryDiagonalCase(x, y)
return (x + y) % 2 == 0
end
def isSecondaryDiagonalCase(x, y)
return (x + y) % 2 == 1
end
def simplifyBySymmetry(x, y)
x = x.abs
y = y.abs
if (y < x)
t = x
x = y
y = t
end
return {x: x, y: y}
end
def getPrimaryDiagonalCaseMoveCount(x, y)
var diagonalOffset = y + x
var diagonalIntersect = diagonalOffset / 2
return ((diagonalIntersect + 2) / 3).floor * 2
end
def getSpecialCaseMoveCount(x, y)
specials = [{
x: 0,
y: 0,
d: 0
},
{
x: 0,
y: 1,
d: 3
},
{
x: 0,
y: 2,
d: 2
},
{
x: 0,
y: 3,
d: 3
},
{
x: 2,
y: 2,
d: 4
},
{
x: 1,
y: 1,
d: 2
},
{
x: 3,
y: 3,
d: 2
}
];
matchingSpecial=nil
specials.each do |special|
if (special[:x] == x && special[:y] == y)
matchingSpecial = special
end
end
if (matchingSpecial)
return matchingSpecial[:d]
end
end
def isVerticalCase(x, y)
return y >= 2 * x
end
def getVerticalCaseMoveCount(x, y)
normalizedHeight = getNormalizedHeightForVerticalGroupCase(x, y)
groupIndex = (normalizedHeight/4).floor
groupStartMoveCount = groupIndex * 2 + x
return groupStartMoveCount + getIndexInVerticalGroup(x, y)
end
def getIndexInVerticalGroup(x, y)
return getNormalizedHeightForVerticalGroupCase(x, y) % 4
end
def getYOffsetForVerticalGroupCase(x)
return x * 2
end
def getNormalizedHeightForVerticalGroupCase(x, y)
return y - getYOffsetForVerticalGroupCase(x)
end
def getSecondaryDiagonalCaseMoveCount(x, y)
diagonalOffset = y + x
diagonalIntersect = diagonalOffset / 2 - 1
return ((diagonalIntersect + 2) / 3).floor * 2 + 1
end
def getMoveCountO1(x, y)
newXY = simplifyBySymmetry(x, y)
x = newXY[:x]
y = newXY[:y]
specialMoveCount = getSpecialCaseMoveCount(x ,y)
if (specialMoveCount != nil)
return specialMoveCount
elsif (isVerticalCase(x, y))
return getVerticalCaseMoveCount(x ,y)
elsif (isPrimaryDiagonalCase(x, y))
return getPrimaryDiagonalCaseMoveCount(x ,y)
elsif (isSecondaryDiagonalCase(x, y))
return getSecondaryDiagonalCaseMoveCount(x ,y)
end
end
def solution(x ,y)
return getMoveCountO1(x, y)
end
puts solution(0,0)
唯一の目的は、誰かが完全なコードを必要とする場合に、誰かがコードを変換する時間を節約することです。
これがJulesMayの関数のPHPバージョンです
function knightDistance($x, $y)
{
$x = abs($x);
$y = abs($y);
if($x < $y)
{
$tmp = $x;
$x = $y;
$y = $tmp;
}
if($x > 2 * $y)
{
$n7 = 0;
$n8 = floor(($x + 2*$y) / 4);
$n10 = floor(($x - 2*$y +1) / 4);
}
else
{
$n7 = floor((2*$y - $x) / 3);
$n8 = floor((2*$x - $y) / 3);
$n10 = 0;
}
$x -= 2 * $n8 + $n7 + 2 * $n10;
$y -= $n8 + 2 * $n7 - $n10;
if($x == 1 && $y == 0)
{
if($n8 > 0)
{
$x = 3;
$y = 1;
$n8--;
}
}
if($x == 2 && $y == 2)
{
if($n8 > 0)
{
$x = 3;
$y = 1;
$n8--;
$n7++;
}
}
$cheatsheet = [[0, 3, 2], [2, 0, 2], [4]];
return $n7 + $n8 + $n10 + $cheatsheet [$y][$x-$y];
}
これは、finitボードで機能するMustafaSerdarŞanlıコードに基づくCバージョンです。
#include <stdio.h>
#include <math.h>
#define test(x1, y1, x2, y2) (sx == x1 && sy == y1 &&tx == x2 &&ty == y2) || (sx == x2 && sy == y2 && tx == x1 && ty==y1)
int distance(int sx, int sy, int tx, int ty) {
int x, y, t;
double delta;
// special corner cases
if (test(1, 1, 2, 2) ||
test(7, 7, 8, 8) ||
test(7, 2, 8, 1) ||
test(1, 8, 2, 7))
return 4;
// axes symmetry
x = abs(sx - tx);
y = abs(sy - ty);
// diagonal symmetry
if (x < y) {
t = x;
x = y;
y = t;
}
// 2 corner cases
if (x == 1 && y == 0)
return 3;
if (x == 2 && y == 2)
return 4;
// main
delta = x - y;
if (y > delta) {
return (int)(delta - 2 * floor((delta - y) / 3));
}
else {
return (int)(delta - 2 * floor((delta - y) / 4));
}
}
ここで、再帰的なソリューションに対する証明を使用してテストします
これが私のプログラムです。これは完璧な解決策ではありません。再帰関数には多くの変更を加える必要があります。しかし、この最終結果は完璧です。少し最適化してみました。
public class KnightKing2 {
private static int tempCount = 0;
public static void main(String[] args) throws IOException {
Scanner in = new Scanner(System.in);
int ip1 = Integer.parseInt(in.nextLine().trim());
int ip2 = Integer.parseInt(in.nextLine().trim());
int ip3 = Integer.parseInt(in.nextLine().trim());
int ip4 = Integer.parseInt(in.nextLine().trim());
in.close();
int output = getStepCount(ip1, ip2, ip3, ip4);
System.out.println("Shortest Path :" + tempCount);
}
// 2 1 6 5 -> 4
// 6 6 5 5 -> 2
public static int getStepCount(int input1, int input2, int input3, int input4) {
return recurse(0, input1, input2, input3, input4);
}
private static int recurse(int count, int tx, int ty, int kx, int ky) {
if (isSolved(tx, ty, kx, ky)) {
int ccount = count+1;
System.out.println("COUNT: "+count+"--"+tx+","+ty+","+ccount);
if((tempCount==0) || (ccount<=tempCount)){
tempCount = ccount;
}
return ccount;
}
if ((tempCount==0 || count < tempCount) && ((tx < kx+2) && (ty < ky+2))) {
if (!(tx + 2 > 8) && !(ty + 1 > 8)) {
rightTop(count, tx, ty, kx, ky);
}
if (!(tx + 2 > 8) && !(ty - 1 < 0)) {
rightBottom(count, tx, ty, kx, ky);
}
if (!(tx + 1 > 8) && !(ty + 2 > 8)) {
topRight(count, tx, ty, kx, ky);
}
if (!(tx - 1 < 0) && !(ty + 2 > 8)) {
topLeft(count, tx, ty, kx, ky);
}
if (!(tx + 1 > 8) && !(ty - 2 < 0)) {
bottomRight(count, tx, ty, kx, ky);
}
if (!(tx - 1 < 0) && !(ty - 2 < 0)) {
bottomLeft(count, tx, ty, kx, ky);
}
if (!(tx - 2 < 0) && !(ty + 1 > 8)) {
leftTop(count, tx, ty, kx, ky);
}
if (!(tx - 2 < 0) && !(ty - 1 < 0)) {
leftBottom(count, tx, ty, kx, ky);
}
}
return count;
}
private static int rightTop(int count, int tx, int ty, int kx, int ky) {
return count + recurse(count + 1, tx + 2, ty + 1, kx, ky);
}
private static int topRight(int count, int tx, int ty, int kx, int ky) {
return count + recurse(count + 1, tx + 1, ty + 2, kx, ky);
}
private static int rightBottom(int count, int tx, int ty, int kx, int ky) {
return count + recurse(count + 1, tx + 2, ty - 1, kx, ky);
}
private static int bottomRight(int count, int tx, int ty, int kx, int ky) {
return count + recurse(count + 1, tx + 1, ty - 2, kx, ky);
}
private static int topLeft(int count, int tx, int ty, int kx, int ky) {
return count + recurse(count + 1, tx - 1, ty + 2, kx, ky);
}
private static int bottomLeft(int count, int tx, int ty, int kx, int ky) {
return count + recurse(count + 1, tx - 1, ty - 2, kx, ky);
}
private static int leftTop(int count, int tx, int ty, int kx, int ky) {
return count + recurse(count + 1, tx - 2, ty + 1, kx, ky);
}
private static int leftBottom(int count, int tx, int ty, int kx, int ky) {
return count + recurse(count + 1, tx - 2, ty - 1, kx, ky);
}
private static boolean isSolved(int tx, int ty, int kx, int ky) {
boolean solved = false;
if ((tx == kx) && (ty == ky)) {
solved = true;
} else if ((tx + 2 == kx) && (ty + 1 == ky)) { // right top
solved = true;
} else if ((tx + 2 == kx) && (ty - 1 == ky)) { // right bottom
solved = true;
} else if ((ty + 2 == ky) && (tx + 1 == kx)) {// top right
solved = true;
} else if ((ty + 2 == ky) && (tx - 1 == kx)) {// top left
solved = true;
} else if ((tx - 2 == kx) && (ty + 1 == ky)) { // left top
solved = true;
} else if ((tx - 2 == kx) && (ty - 1 == ky)) {// left bottom
solved = true;
} else if ((ty - 2 == ky) && (tx + 1 == kx)) { // bottom right
solved = true;
} else if ((ty - 2 == ky) && (tx - 1 == kx)) { // bottom left
solved = true;
}
return solved;
}
}
これが別の実用的なPythonソリューションです（Johan du Toitから）：
入力：
1<=sx,sy,tx,ty<=8
def knightDistance( sx, sy, tx, ty):
def test(x1, y1, x2, y2):
return (sx == x1 and sy == y1 and tx == x2 and ty == y2) or (sx == x2 and sy == y2 and tx == x1 and ty==y1)
# special corner cases
if (test(1, 1, 2, 2) or
test(7, 7, 8, 8) or
test(7, 2, 8, 1) or
test(1, 8, 2, 7)):
return 4
# axes symmetry
x = abs(sx - tx)
y = abs(sy - ty)
# diagonal symmetry
if (x < y):
x,y = y,x
# 2 corner cases
if (x == 1 and y == 0):
return 3
if (x == 2 and y == 2):
return 4
# main
delta = x - y;
if (y > delta) :
return int(delta - 2 * ((delta - y) // 3))
else:
return int(delta - 2 * ((delta - y) // 4))