圖的深度優(yōu)先遍歷思想
圖的遍歷通常有兩種遍歷次序方案: 深度優(yōu)先遍歷和廣度優(yōu)先遍歷钧萍。
深度優(yōu)先遍歷（DepthFirstSearch）也有稱為深度優(yōu)先搜索：簡(jiǎn)稱DFS狈邑。
它的具體思想類似于在一個(gè)房間里面找鑰匙的方案： 無論從哪一間房間開始都可以蹂匹，將房間內(nèi)的墻角碘菜，床頭，床下限寞，衣柜忍啸，電視柜等挨個(gè)尋找，做到不放過任何一個(gè)死角履植，接著再尋找下一個(gè)房間计雌。
馬踏棋盤算法（騎士周游問題）
題目淵源：
馬踏棋盤問題（又稱騎士周游或騎士漫游問題）是算法設(shè)計(jì)的經(jīng)典問題之一。
題目要求：
國(guó)際象棋的棋盤為8*8的方格棋盤玫霎，現(xiàn)將“馬”放在任意指定的方格中凿滤，按照“馬”走棋的規(guī)則將“馬進(jìn)行移動(dòng)。要求每個(gè)方格只能進(jìn)入一次庶近，最終使得“馬”走遍棋盤64個(gè)方格翁脆。
編寫代碼，實(shí)現(xiàn)馬踏棋盤的操作鼻种，要求用1-64來標(biāo)注“馬”移動(dòng)的路徑反番。
圖片.png
解決問題借鑒的思路：
- 回溯法：
回溯法的直到實(shí)現(xiàn)很簡(jiǎn)單，就是一條路走到黑，碰壁了再回來一條路走到黑...一般和遞歸可以很好的搭配使用罢缸，還有深度優(yōu)先搜索（DFS）篙贸。 - 哈密爾頓路徑：
圖G中的哈密爾頓路徑指的是經(jīng)過圖G中的每個(gè)頂點(diǎn)，且只經(jīng)過一次的一條軌跡枫疆，如果這條軌跡是一條閉合路徑（從起點(diǎn)出發(fā)不重復(fù)的遍歷所有有點(diǎn)后仍能回到起點(diǎn)）爵川，那么這條路經(jīng)稱為哈密爾頓回路。
代碼實(shí)現(xiàn)
#include "stdafx.h"
#include<stdio.h>
#include<time.h>
#define X 8
#define Y 8
int chess[X][Y];
//找到基于(x,y)位置的下一個(gè)可走的位置
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");
}
//深度優(yōu)先遍歷棋盤的算法
//(x, y)為起始位置的坐標(biāo)
//tag是標(biāo)記變量, 每走一步 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);
}
//找到馬下一個(gè)可走坐標(biāo)(x1, y1) 如果找到flag=1 否則為0
while (flag)
{
if (TravelChessBoard(x1, y1, tag + 1)) {
return 1;
}
//繼續(xù)找到馬下一個(gè)可走坐標(biāo)(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本次計(jì)算一共耗時(shí):%f秒\n\n", (double)(finish - start) / CLOCKS_PER_SEC);
getchar();
getchar();
return 0;
}
