图的深度优先遍历思想
图的遍历通常有两种遍历次序方案: 深度优先遍历和广度优先遍历。
深度优先遍历（DepthFirstSearch）也有称为深度优先搜索：简称DFS。
它的具体思想类似于在一个房间里面找钥匙的方案： 无论从哪一间房间开始都可以，将房间内的墙角，床头，床下，衣柜，电视柜等挨个寻找，做到不放过任何一个死角，接着再寻找下一个房间。
马踏棋盘算法（骑士周游问题）
题目渊源：
马踏棋盘问题（又称骑士周游或骑士漫游问题）是算法设计的经典问题之一。
题目要求：
国际象棋的棋盘为8*8的方格棋盘，现将“马”放在任意指定的方格中，按照“马”走棋的规则将“马进行移动。要求每个方格只能进入一次，最终使得“马”走遍棋盘64个方格。
编写代码，实现马踏棋盘的操作，要求用1-64来标注“马”移动的路径。
图片.png
解决问题借鉴的思路：
- 回溯法：
回溯法的直到实现很简单，就是一条路走到黑，碰壁了再回来一条路走到黑...一般和递归可以很好的搭配使用，还有深度优先搜索（DFS）。 - 哈密尔顿路径：
图G中的哈密尔顿路径指的是经过图G中的每个顶点，且只经过一次的一条轨迹，如果这条轨迹是一条闭合路径（从起点出发不重复的遍历所有有点后仍能回到起点），那么这条路经称为哈密尔顿回路。
代码实现
#include "stdafx.h"
#include<stdio.h>
#include<time.h>
#define X 8
#define Y 8
int chess[X][Y];
//找到基于(x,y)位置的下一个可走的位置
int nextxy(int *x, int *y, int count) {
switch (count)
{
case 0:
if (*x + 2 <= X -1 && *y - 1 >= 0 && chess[*x + 2][*y - 1] == 0)
{
*x += 2;
*y -= 1;
return 1;
}
break;
case 1:
if (*x + 2 <= X - 1 && *y + 1 <= Y -1 && chess[*x + 2][*y + 1] == 0)
{
*x += 2;
*y += 1;
return 1;
}
break;
case 2:
if (*x + 1 <= X - 1 && *y - 2 >= 0 && chess[*x + 1][*y - 2] == 0)
{
*x = *x + 1;
*y = *y - 2;
return 1;
}
break;
case 3:
if (*x + 1 <= X - 1 && *y + 2 <= Y -1 && chess[*x + 1][*y + 2] == 0)
{
*x = *x + 1;
*y = *y + 2;
return 1;
}
break;
case 4:
if (*x - 2 >= 0 && *y - 1 >= 0 && chess[*x - 2][*y - 1] == 0)
{
*x = *x - 2;
*y = *y - 1;
return 1;
}
break;
case 5:
if (*x - 2 >= 0 && *y + 1 <= Y - 1 && chess[*x - 2][*y + 1] == 0)
{
*x = *x - 2;
*y = *y + 1;
return 1;
}
break;
case 6:
if (*x - 1 >= 0 && *y - 2 >= 0 && chess[*x - 1][*y - 2] == 0)
{
*x = *x - 1;
*y = *y - 2;
return 1;
}
break;
case 7:
if (*x - 1 >= 0 && *y + 2 <= Y - 1 && chess[*x - 1][*y + 2] == 0)
{
*x = *x - 1;
*y = *y + 2;
return 1;
}
break;
default:
break;
}
return 0;
}
void printc() {
int i, j;
for (i = 0; i < X; i++)
{
for (j = 0; j < Y; j++)
{
printf("%2d\t", chess[i][j]);
}
printf("\n");
}
printf("\n");
}
//深度优先遍历棋盘的算法
//(x, y)为起始位置的坐标
//tag是标记变量, 每走一步 tag + 1
int TravelChessBoard(int x, int y, int tag) {
int x1 = x, y1 = y, flag = 0, count = 0;
chess[x][y] = tag;
if (X * Y <= tag)
{
printc();
//打印棋盘
return 1;
}
flag = nextxy(&x1, &y1, count);
while (0 == flag && count < 7)
{
count++;
flag = nextxy(&x1, &y1, count);
}
//找到马下一个可走坐标(x1, y1) 如果找到flag=1 否则为0
while (flag)
{
if (TravelChessBoard(x1, y1, tag + 1)) {
return 1;
}
//继续找到马下一个可走坐标(x1, y1) 如果找到flag=1 否则为0
x1 = x;
y1 = y;
count++;
flag = nextxy(&x1, &y1, count);
while (0 == flag && count < 7)
{
count++;
flag = nextxy(&x1, &y1, count);
}
}
if (0 == flag)
{
chess[x][y] = 0;
}
return 0;
}
int main() {
int i, j;
clock_t start, finish;
start = clock();
for (i = 0; i < X; i++) {
for (j = 0; j < Y; j++)
{
chess[i][j] = 0;
}
}
if (!TravelChessBoard(2, 0, 1))
{
printf("抱歉,马踏棋盘失败");
}
finish = clock();
printf("\n本次计算一共耗时:%f秒\n\n", (double)(finish - start) / CLOCKS_PER_SEC);
getchar();
getchar();
return 0;
}
