図の遍歴アルゴリズム-馬遍歴盤

タイトル
n*mの碁盤の中で、馬は日を歩くしかなく、馬は位置(x,y)から出発して、碁盤のすべての点を1回歩いて、しかも1回だけ歩いて、すべての経路を見つけます.
demo実装
碁盤は5*4、初期位置は(0.0)
アルゴリズムの重点
さかのぼる
再帰後に座標を初期状態0にします.パスが間違っている場合、パスを歩く前の状態に戻すことができます.
具体的な実装は,注釈にはっきりと書かれている.

#include

using namespace std;

//             
//       ，   for   
int fx[8]= {1,2,2,1,-1,-2,-2,-1};
int fy[8]= {2,1,-1,-2,-2,-1,1,2};

static int mCount;
const static int n=5,m=4;
int a[n][m];  // int           

void mFind(int x,int y,int dep);//       
int mCheck(int x,int y);//        ，      
void output();//    

int main()
{
    int x=0,y=0;//  (0,0)    
    mCount=0;
    for(int i=0; ifor(int j=0; j0;
    a[x][y]=1;

    mFind(x,y,2);

    if(mCount==0)
        cout<<"Non solution"<else
        cout<"final count = "<void mFind(int x,int y,int dep)
{
    int xx,yy;
    for(int i=0; i<8; i++)
    {
        xx=x+fx[i];
        yy=y+fy[i];
        if(mCheck(xx,yy)==1)
        {
            a[xx][yy]=dep;
            if(dep==n*m)
                output();    //     n*m，        ，   
            else
                mFind(xx,yy,dep+1);
            a[xx][yy]=0;     //  ，      。（    ，         ）
        }
    }
}

int mCheck(int x,int y)
{
    //        ，      
    if(x<0||y<0||x>=n||y>=m||a[x][y]!=0)
        return 0;
    return 1;
}

void output()
{
    mCount++;
    cout<cout<<"count= "<for(int i=0; icout<for(int j=0; jcout<" ";
}
}