0

我的代码在这里：问题是在 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 棋盘中从一个方格到另一个方格的代码。我的代码在某些情况下给出了错误的答案：

a[xs][ys]=1；是为了防止循环。例如 (0,7) ->>>> (5,2) 的答案是 4 但我的算法给出 38 。MY坐标轴是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;
    }
4

1 回答 1

3

从数据结构的角度思考而不是从算法的角度思考通常是有益的。

在这种情况下，棋盘上马的有效走法构成无向图 G，其中顶点表示棋盘位置，边表示有效走法。因此，您可能有节点 a1 和 b3 通过一条边连接，因为骑士可能从 a1 移动到 b3，反之亦然。

鉴于该问题的表示，计算骑士从 A 到 B 的最小移动数相当容易，因为它是 G 中从节点 A 到节点 B 的最短路径的长度。

  • 要计算给定起始节点和所有结束节点的最短路径，请使用时间复杂度 O(|V||E|) 的 Bellman-Ford 算法。
  • 要计算所有节点对的最短路径，请使用时间复杂度 O(|V|^3) 的 Floyd-Warshall 算法。
于 2012-12-14T11:47:48.733 回答