|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
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");
- }
复制代码 |
评分
-
查看全部评分
|