KNight MOVe shortest

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棋盘上从一个方块遍历到另一个方块的代码。对于某些情况，我的代码给出了错误的答案：

axs=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的最小移动次数相当容易，因为它是G中从节点A到节点B的最短路径的长度。

• 要计算给定起始节点和所有结束节点的最短路径，请使用时间复杂度为O(|V||E|)的贝尔曼-福特算法。
• 要计算所有节点对的最短路径，请使用时间复杂度为O(|V|^3)的

-

• 算法。