题目

假设象棋棋盘有5*5共25个格子，设计一个程序，使棋子从初始位置左上角开始跳马，能够把棋盘的格子全部都走一遍，每个格子只允许走一次。
(a)输出一个解，用矩阵表示。
(b)求总共有多少解。

输出样例

 1 16 11  6  3 
10  5  2 15 12 
22 14 17  4  7 
20  9 23 13 18 
25 21 19  8 24 

304

题解

DFS
把马能跳的位置都遍历一下

代码

#include<iostream>
using namespace std;
#include<algorithm>
const int N=10;
int dx[8]={-1,-2,-2,-1,1,2,2,1},dy[8]={-2,-1,1,2,2,1,-1,-2};//所有可能跳的向量
int G[N][N],res;
int prt[N][N],step=1;//step表示当前是第几跳，输出用
bool st[N][N];//足迹数组，st[i][j]=true表示走过了
bool isfull(){//判断st数组是否足迹都走遍了
    for(int i=1;i<=5;i++){
        for(int j=1;j<=5;j++){
            if(!st[i][j]) return false;
        }
    }
    return true;
}
void dfs_p(int x,int y){//输出一个解用
    prt[x][y]=step++;
    st[x][y]=true;
    int a,b;
    bool flag=false;
    for(int k=0;k<8;k++){
        a=x+dx[k],b=y+dy[k];
        if(a>=1&&a<=5&&b>=1&&b<=5&&!st[a][b]) dfs_p(a,b),flag=true;
    }
    if(!flag&&isfull()) return;

}
void dfs(int x,int y){//求一共的解res
    st[x][y]=true;
    int a,b;
    bool flag=false;//flag记录在当前dfs层是否有一个位置还可跳
    for(int k=0;k<8;k++){//八个可能位置挨个判断
        a=x+dx[k],b=y+dy[k];
        if(a>=1&&a<=5&&b>=1&&b<=5&&!st[a][b]) dfs(a,b),flag=true;
    }
    if(!flag&&isfull()) res++;//无处可去了且跳满了 res++
    st[x][y]=false;//回复现场
}
int main(void){
    dfs_p(1,1);
    for(int i=1;i<=5;i++){
        for(int j=1;j<=5;j++){
            printf("%2d ",prt[i][j]);
        }
        cout<<endl;
    }
    cout<<endl;
    memset(st,false,sizeof st);//恢复st
    dfs(1,1);
    cout<<res;

}