《数据结构与算法》——图的遍历搜索
DFS:从图中任意一点开始,按照特点规则(如先往右手侧的边走)遍历每一条边,每经过一个点,就标记一次,当遇到标记过的点就返回到上一个点
马踏棋盘问题:
本问题算法核心在于合理的利用递归来遍历二维数组,这里的图是利用一个二维数组来实现和表示的。通过遍历,马在棋盘任意位置可以移动的位置最多有8个,我们要做的就是不断地找到这些可能的位置,一直到某一个位置无法移动,返回函数至上一个位置,选择其他可能移动的位置,直至找到一个可能的移动路径完成对棋盘所有位置的移动。
附上马踏棋盘的代码:
#include<cstdio>
#include<cstdlib>
#include<time.h>
#include<iostream>
using namespace std;
#define X 8
#define Y 8
int chess;
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 == 0)
{
*x = x1 - 1;
*y = y1 - 2;
return 1;
}
break;
case 1:
if (x1 + 1 <= X-1 && y1 - 2 >= 0 && chess == 0)
{
*x = x1 + 1;
*y = y1 - 2;
return 1;
}
break;
case 2:
if (x1 + 2 <= X - 1 && y1 - 1 >= 0 && chess == 0)
{
*x = x1 + 2;
*y = y1 - 1;
return 1;
}
break;
case 3:
if (x1 + 2 <= X - 1 && y1 + 1 <= Y - 1 && chess == 0)
{
*x = x1 + 2;
*y = y1 + 1;
return 1;
}
break;
case 4:
if (x1 + 1 <= X - 1 && y1 + 2 <= Y - 1 && chess == 0)
{
*x = x1 + 1;
*y = y1 + 2;
return 1;
}
break;
case 5:
if (x1 - 1 >= 0 && y1 + 2 <= Y - 1 && chess == 0)
{
*x = x1 - 1;
*y = y1 + 2;
return 1;
}
break;
case 6:
if (x1 - 2 >= 0 && y1 + 1 <= Y-1 && chess == 0)
{
*x = x1 - 2;
*y = y1 + 1;
return 1;
}
break;
case 7:
if (x1 - 2 >= 0 && y1 - 1 >= 0 && chess == 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);
}
cout << endl;
}
cout << endl;
}
//搜素下一步
int TravelChess(int x, int y, int tag)
{
int count = 0, flag = 0;
int x1 = x, y1 = y;
chess = 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 = 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");
}
页:
[1]