c++解马走日

解题思路:

注意事项:

参考代码:

//马走日经典应用 

#include<iostream>

#include<cstdio>

#include<cstring>

#include<vector>

using namespace std;

const int N = 15;//自定义标志数组的最大值 

int cnt,n,m;//cnt标记次数 ,n ,m表示棋盘大小 

int dx[9] = {0,1,1,-1,-1,2,2,-2,-2};//马走日的八种走法所罗列出来的x变化 

int dy[9] = {0,2,-2,2,-2,1,-1,1,-1};//马走日的八种走法所罗列出来的x变化

bool v[N][N];//标志数组 

void dfs(int i,int j,int step){

if(step == n * m + 1) cnt++;//判断是不是走完所有的道路 

else{

for(int k = 1; k <= 8;k++){

int x = i + dx[k];//遍历x,y变化的所有情况 

int y = j + dy[k];

//判断x和y的变化会不会跑出边界之外并且是不是还没走过 

if(!v[x][y] && x >= 0 && x < n && y >= 0 && y < m){

v[x][y] = 1;

dfs(x,y,step + 1);//步长加一 ,递归 

v[x][y] = 0;//消除标记方便其他步骤去通过这个地方 

}

}

}

}

int main(){

int t;

scanf("%d",&t);

while(t--){

cnt = 0;

memset(v,0,sizeof(v));//清零数组 

int x_s,y_s;

scanf("%d %d %d %d",&n,&m,&x_s,&y_s);

v[x_s][y_s] = 1;//从起点出发

dfs(x_s,y_s,2);//步长加一 

cout<<cnt<<endl;

}

}