骑士的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）。