骑士游历2

Description

设有一个n×n的棋盘（n≤10），在棋盘上的任意一点A(x,y)有一中国象棋<马>,<马>走的规则同前，但取消<马>只能向右走的条件。试找出一条路径，使<马>不重复地走遍棋盘上的每一个点。其中左下角的坐标为(1,1)右上解的从标为(n,n)。

Sample Input

6
3 4

Sample Output（输出任意一种）

36   13   10   23    4   15
11   22    5   14    9   24
20   35   12    1   16    3
29   32   21    6   25    8
34   19   30   27    2   17
31   28   33   18    7   26

解题思路

使用搜索找出任意一种方案

#include<iostream>
#include<iomanip>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
const int maxn=30;
const int dx[10]={
   0,-2,-1,2,-1,1,-2,2,1};
const int dy[10]={
   0,-1,-2,1,2,2,1,-1,-2};//定义马走的八个方向
int a[maxn+2][maxn+2],m,n,t=0,s=0,k;
void DFS(int x,int y,int dep)
{
   
	if(dep>=k*k)
	{
   
		
		for(int i=1;i<=k;i++)
		{
   
			for(int j=1;j<=k;j++)
			 cout<<setw(5)<<a[i][j];//输出
			cout<<endl;
		} 
		exit(0);//直接退出
	}
	for(int i=1;i<=8;i++)
	{
   
		if(x+dx[i]>0&&x+dx[i]<=k&&y+dy[i]>0&&y+dy[i]<=k)//判断是否会越界
		 if(a[x+dx[i]][y+dy[i]]==0)
		 {
   
		 	a[x+dx[i]][y+dy[i]]=dep+1;//赋值
		 	DFS(x+dx[i],y+dy[i],dep+1);//继续搜索
		 	a[x+dx[i]][y+dy[i]]=0;//回溯
		 }
	}
}
int main()
{
   
	cin>>k;
	cin>>n>>m;
	memset(a,0,sizeof(a));
	a[n][m]=1;
	DFS(n,m,1);
	return 0;
}

附：骑士游历1