《数据结构与算法》——图的遍历搜索

luciferzf

DFS：
从图中任意一点开始，按照特点规则（如先往右手侧的边走）遍历每一条边，每经过一个点，就标记一次，当遇到标记过的点就返回到上一个点

马踏棋盘问题：
本问题算法核心在于合理的利用递归来遍历二维数组，这里的图是利用一个二维数组来实现和表示的。通过遍历，马在棋盘任意位置可以移动的位置最多有8个，我们要做的就是不断地找到这些可能的位置，一直到某一个位置无法移动，返回函数至上一个位置，选择其他可能移动的位置，直至找到一个可能的移动路径完成对棋盘所有位置的移动。

附上马踏棋盘的代码：

#include<cstdio>
#include<cstdlib>
#include<time.h>
#include<iostream>
using namespace std;

#define X 8
#define Y 8
int chess[X][Y];
int a = 0;

//验证下一步是否可行
int IsHaveNext(int *x, int *y, int counts)
{
        int x1=*x, y1=*y;
        switch (counts)
        {
        case 0:
                if (x1 - 1 >= 0 && y1 - 2 >= 0 && chess[x1 - 1][y1 - 2] == 0)
                {
                        *x = x1 - 1;
                        *y = y1 - 2;
                        return 1;
                }
                break;
        case 1:
                if (x1 + 1 <= X-1 && y1 - 2 >= 0 && chess[x1 + 1][y1 - 2] == 0)
                {
                        *x = x1 + 1;
                        *y = y1 - 2;
                        return 1;
                }
                break;
        case 2:
                if (x1 + 2 <= X - 1 && y1 - 1 >= 0 && chess[x1 + 2][y1 - 1] == 0)
                {
                        *x = x1 + 2;
                        *y = y1 - 1;
                        return 1;
                }
                break;
        case 3:
                if (x1 + 2 <= X - 1 && y1 + 1 <= Y - 1 && chess[x1 + 2][y1 + 1] == 0)
                {
                        *x = x1 + 2;
                        *y = y1 + 1;
                        return 1;
                }
                break;
        case 4:
                if (x1 + 1 <= X - 1 && y1 + 2 <= Y - 1 && chess[x1 + 1][y1 + 2] == 0)
                {
                        *x = x1 + 1;
                        *y = y1 + 2;
                        return 1;
                }
                break;
        case 5:
                if (x1 - 1 >= 0 && y1 + 2 <= Y - 1 && chess[x1 - 1][y1 + 2] == 0)
                {
                        *x = x1 - 1;
                        *y = y1 + 2;
                        return 1;
                }
                break;
        case 6:
                if (x1 - 2 >= 0 && y1 + 1 <= Y-1 && chess[x1 -2][y1 + 1] == 0)
                {
                        *x = x1 - 2;
                        *y = y1 + 1;
                        return 1;
                }
                break;
        case 7:
                if (x1 - 2 >= 0 && y1 - 1 >= 0 && chess[x1 - 2][y1 - 1] == 0)
                {
                        *x = x1 - 2;
                        *y = y1 - 1;
                        return 1;
                }
                break;
        defaule:
                break;
        }
        return 0;
}

//打印棋盘
void print()
{
        for (int i = 0; i < X; i++)
        {
                for (int j = 0; j < Y; j++)
                {
                        printf("%3d", chess[i][j]);
                }
                cout << endl;
        }
        cout << endl;
}

//搜素下一步
int TravelChess(int x, int y, int tag)
{
        int count = 0, flag = 0;
        int x1 = x, y1 = y;
        chess[x1][y1] = tag;
        if (X*Y == tag)
        {
                print();//打印棋盘
                return 1;
        }

        while (flag!=1&&count <= 7)
        {
                flag = IsHaveNext(&x1, &y1, count);
                count++;
        }

        while (flag)
        {
                if (TravelChess(x1, y1, tag+1))
                {
                        return 1;
                }
                x1 = x, y1 = y;
                flag = 0;
                while (flag != 1 && count <= 7)
                {
                        flag = IsHaveNext(&x1, &y1, count);
                        count++;
                }
        }

        if (flag == 0)
        {
                chess[x][y] = 0;

        }
        return 0;
}

int main()
{
        clock_t s, e;
        int x, y;
        cout << "input the initial position:" << endl;
        cin >> x;
        cin >> y;
        s = clock();
        if (!TravelChess(x, y, 1))
        {
                cout << "Failed !" << endl;
        }

        e = clock();
        cout <<endl<< "used time = " << (double)(e - s) / CLOCKS_PER_SEC << endl;

        system("PAUSE");
}