C++骑士巡游问题_c++1438: 【基础】骑士巡游

一个骑士在棋盘中，给予其一个初始位置，求其能否不重复地走完整个棋盘。

#include"stdafx.h"
#include<iostream>
#include<vector>
using namespace std;
#define size 6//棋盘规格
int visit=0;//访问顺序
vector<vector<int>>mark;//定义棋盘
const int dx[8]={-1,-2,-2,-1,1,2,2,1};//方向数组
const int dy[8]={-2,-1,1,2,2,1,-1,-2};
void print(vector<vector<int>>mark)//打印棋盘
{
     for(int i=0;i<size;++i)
     {
         for(int j=0;j<size;++j)
         {
             cout<<mark[i][j]<<"\t";
         }
         cout<<endl<<endl;
     }
	 cout<<endl<<endl;
}
int waysum(int x,int y)//记录当前点有多少条路可走
{
	int sum=0;
	for(int i=0;i<8;i++)//8个方向
	{
		int tempx=x+dx[i];
		int tempy=y+dy[i];
		if(tempx>=0&&tempx<size&&tempy>=0&&tempy<size&&mark[tempx][tempy]==0)//坐标未越界
			sum++;
	}
	return sum;
}
bool knightTour(int x,int y)
{
	visit++;//当前点已经遍历
	mark[x][y]=visit;//遍历的顺序
	if(visit==size*size)//全部遍历到则成功
		return true;
	vector<int> a;
	vector<vector<int>>point;//记录可以访问的点
	int sum=0,nextsum=0;//当前可以访问的路径条数，和选择一点后，下一次可以访问的路径条数
	int tempx,tempy;
	int nextx,nexty;//保存下一次选择的点
	int minway=size+1;//记录所需最少路径条数
	for(int i=0;i<8;i++)//8个方向进行试探
	{
		tempx=x+dx[i];
		tempy=y+dy[i];
		if(tempx>=0&&tempx<size&&tempy>=0&&tempy<size&&mark[tempx][tempy]==0)
		{
			a.push_back(tempx);
			a.push_back(tempy);
			point.push_back(a);//保存可访问点的坐标
			sum++;//可访问点数目+1
			nextsum=waysum(tempx,tempy);
			if(nextsum<minway)//每次都选择下一次路径最少那个点去访问
			{
				minway=nextsum;
				nextx=tempx;
				nexty=tempy;
			}
		}
	}
	bool flag=false;//标记是否成功访问
	if(sum==0)//此时无路可走，撤销当前点的访问
	{
		visit--;
		mark[x][y]=0;
		return false;
	}
	else//当前点可走，则走下一点
	{
		flag=knightTour(nextx,nexty);//更新flag
		if(flag)return true;//成功访问则返回true
		else//否则遍历访问可访问的所有点
		{
			for(int i=0;i<sum;i++)
			{
				flag=knightTour(point[i][0],point[i][1]);
				if(flag)return true;
			}
		}
	}
	//若遍历完所有点都无法成功则返回false
	visit--;
	mark[x][y]=0;
	return false;
}
int main()
{
	for(int i=0;i<size;i++)//初始化棋盘
	{
		mark.push_back(vector<int>());
		for(int j=0;j<size;j++)
			mark[i].push_back(0);
	}
	knightTour(1,2);
	print(mark);
	system("pause");
	return 0;
}
/*学习笔记，侵删。*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103

执行结果