騎士的MOVe最短

Question

我的代碼是在這裏：問題是要找到最小數量的舉動從一個平方要到8級* 8的國際象棋棋盤等。

#include<iostream> 
    using namespace std; 
    int n; 
    int a[12][12]; 
    int min1=1000,xd=5,yd=2,ys,xs,xsi,ysi; 

    int find_path(int xs,int ys) 
    { 
     cout<<xs<<" "<<ys<<endl; 
    if((xs==xd) && (ys==yd)) { cout<<"destiny schieved "<<endl; return 0;}  
    if(a[xs][ys]==1 || xs<0 || ys<0 || xs>7 || ys>7) return 10000; 
    a[xs][ys]=1; 
    int a1=1+(find_path(xs-2,ys+1)) ; 
    int b=1+(find_path(xs-2,ys-1)) ; 
    int c=1+(find_path(xs-1,ys+2)) ; 
    int d=1+(find_path(xs-1,ys-2)) ; 
    int d=1+(find_path(xs+2,ys+1)) ; 
    int e=1+(find_path(xs+2,ys-1)) ; 
    int f=1+(find_path(xs+1,ys+2)) ; 
    int g=1+(find_path(xs+1,ys-2)) ; 
    a[xs][ys]=0; 
    return min(a1,b,c,d,e,f,g); 
    } 


    int main() 
    { 
     int i,j,k; 

     for(i=0;i<8;i++) 
     for(j=0;j<8;j++) 
     a[i][j]=0; 

    cout<<"start"<<endl; 

    cout<<find_path(0,7); 

     system("pause"); 
     return 0; 
     } 

這是我在8 * 8棋盤上從一個方塊移動到另一個方塊的代碼。 MY代碼給出了一些情況下錯誤的答案：

一個[XS] [YS] = 1;是爲了防止循環。 用於如答案（0,7） - >>>>（5,2）是4，但我的算法中給出了38。我的座標軸是X：從左到右，Y軸：從上到下。請幫我解決我的問題。

幾個解決方案是：

（7,0） - >>>（0,7）：6 （0,7） - >>>（5,2）：4

我也嘗試過這是我後來編輯以得到上面的代碼中的另一個代碼：

int find_path(int xs,int ys,int path) 
    { 
     cout<<xs<<" "<<ys<<endl; 
    if((xs==xd) && (ys==yd)) { if(min1>path) min1=path; cout<<"destiny schieved "<<path<<endl; return 1;}  
    if(a[xs][ys]==1 || xs<0 || ys<0 || xs>7 || ys>7) return 0; 
    a[xs][ys]=1; 
    if(find_path(xs-2,ys+1,path+1)) {if(path==0) {cout<<"i am on start1"<<endl;} else return 1;} 
    if(find_path(xs-2,ys-1,path+1)) {if(path==0) {cout<<"i am on start2"<<endl;} else return 1; } 
    if(find_path(xs-1,ys+2,path+1)) {if(path==0) {cout<<"i am on start3"<<endl;} else return 1; } 
    if(find_path(xs-1,ys-2,path+1)) {if(path==0) {cout<<"i am on start4"<<endl;} else return 1;} 
    if(find_path(xs+2,ys+1,path+1)) {if(path==0) {cout<<"i am on start5"<<endl;} else return 1;} 
    if(find_path(xs+2,ys-1,path+1)) {if(path==0) {cout<<"i am on start6"<<endl;} else return 1;} 
    if(find_path(xs+1,ys+2,path+1)) {if(path==0) {cout<<"i am on start7"<<endl;} else return 1; } 
    if(find_path(xs+1,ys-2,path+1)) {if(path==0) {cout<<"i am on start8"<<endl;} else return 1; } 
    a[xs][ys]=0; 
    return 0; 
    } 

Answer 1

它往往獎勵認爲在數據結構，而不是在算法思維的條款。

在這種情況下，對於一個騎士的有效移動在基板上構成的無向圖G，其中頂點表示板的位置和邊表示有效移動。因此，你可能有節點a1和b3連接一個邊緣，因爲騎士可能會從a1移動到b3，反之亦然。

鑑於問題的該表示，這是相當容易計算的分鐘數的移動用於騎士從A轉到B，因爲它是最短路徑從節點A在G.

長度到節點B

• 計算給定開始節點和所有末端節點的最短路徑，使用時間複雜度爲O（| V || E |）的Bellman-Ford算法。
• 來計算所有節點對的最短路徑，可以使用Floyd-Warshall算法隨時間複雜度爲O（| V |^3）。