0

私のコードはここにあります: 質問は、8*8 チェス盤で 1 つの正方形から別の正方形に移動する最小移動数を見つけることです。

    #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 のチェス盤で 1 つの正方形から別の正方形にトラバースするための私のコードです。私のコードは、場合によっては間違った答えを出します:

a[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;
    }
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 に答える