图的深度优先遍历和马踏棋盘算法

图的深度优先遍历思想

图的遍历通常有两种遍历次序方案: 深度优先遍历和广度优先遍历。
深度优先遍历（DepthFirstSearch）也有称为深度优先搜索：简称DFS。
它的具体思想类似于在一个房间里面找钥匙的方案： 无论从哪一间房间开始都可以，将房间内的墙角，床头，床下，衣柜，电视柜等挨个寻找，做到不放过任何一个死角，接着再寻找下一个房间。

马踏棋盘算法（骑士周游问题）

题目渊源：
马踏棋盘问题（又称骑士周游或骑士漫游问题）是算法设计的经典问题之一。
题目要求：
国际象棋的棋盘为8*8的方格棋盘，现将“马”放在任意指定的方格中，按照“马”走棋的规则将“马进行移动。要求每个方格只能进入一次，最终使得“马”走遍棋盘64个方格。
编写代码，实现马踏棋盘的操作，要求用1-64来标注“马”移动的路径。

图片.png

解决问题借鉴的思路：

1. 回溯法：
   回溯法的直到实现很简单，就是一条路走到黑，碰壁了再回来一条路走到黑...一般和递归可以很好的搭配使用，还有深度优先搜索（DFS）。
2. 哈密尔顿路径：
   图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;
}