鱼C论坛

 找回密码
 立即注册
查看: 2377|回复: 0

[学习笔记] 《数据结构与算法》——图的遍历搜索

[复制链接]
发表于 2017-8-17 14:01:45 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

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

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

附上马踏棋盘的代码:
  1. #include<cstdio>
  2. #include<cstdlib>
  3. #include<time.h>
  4. #include<iostream>
  5. using namespace std;

  6. #define X 8
  7. #define Y 8
  8. int chess[X][Y];
  9. int a = 0;

  10. //验证下一步是否可行
  11. int IsHaveNext(int *x, int *y, int counts)
  12. {
  13.         int x1=*x, y1=*y;
  14.         switch (counts)
  15.         {
  16.         case 0:
  17.                 if (x1 - 1 >= 0 && y1 - 2 >= 0 && chess[x1 - 1][y1 - 2] == 0)
  18.                 {
  19.                         *x = x1 - 1;
  20.                         *y = y1 - 2;
  21.                         return 1;
  22.                 }
  23.                 break;
  24.         case 1:
  25.                 if (x1 + 1 <= X-1 && y1 - 2 >= 0 && chess[x1 + 1][y1 - 2] == 0)
  26.                 {
  27.                         *x = x1 + 1;
  28.                         *y = y1 - 2;
  29.                         return 1;
  30.                 }
  31.                 break;
  32.         case 2:
  33.                 if (x1 + 2 <= X - 1 && y1 - 1 >= 0 && chess[x1 + 2][y1 - 1] == 0)
  34.                 {
  35.                         *x = x1 + 2;
  36.                         *y = y1 - 1;
  37.                         return 1;
  38.                 }
  39.                 break;
  40.         case 3:
  41.                 if (x1 + 2 <= X - 1 && y1 + 1 <= Y - 1 && chess[x1 + 2][y1 + 1] == 0)
  42.                 {
  43.                         *x = x1 + 2;
  44.                         *y = y1 + 1;
  45.                         return 1;
  46.                 }
  47.                 break;
  48.         case 4:
  49.                 if (x1 + 1 <= X - 1 && y1 + 2 <= Y - 1 && chess[x1 + 1][y1 + 2] == 0)
  50.                 {
  51.                         *x = x1 + 1;
  52.                         *y = y1 + 2;
  53.                         return 1;
  54.                 }
  55.                 break;
  56.         case 5:
  57.                 if (x1 - 1 >= 0 && y1 + 2 <= Y - 1 && chess[x1 - 1][y1 + 2] == 0)
  58.                 {
  59.                         *x = x1 - 1;
  60.                         *y = y1 + 2;
  61.                         return 1;
  62.                 }
  63.                 break;
  64.         case 6:
  65.                 if (x1 - 2 >= 0 && y1 + 1 <= Y-1 && chess[x1 -2][y1 + 1] == 0)
  66.                 {
  67.                         *x = x1 - 2;
  68.                         *y = y1 + 1;
  69.                         return 1;
  70.                 }
  71.                 break;
  72.         case 7:
  73.                 if (x1 - 2 >= 0 && y1 - 1 >= 0 && chess[x1 - 2][y1 - 1] == 0)
  74.                 {
  75.                         *x = x1 - 2;
  76.                         *y = y1 - 1;
  77.                         return 1;
  78.                 }
  79.                 break;
  80.         defaule:
  81.                 break;
  82.         }
  83.         return 0;
  84. }

  85. //打印棋盘
  86. void print()
  87. {
  88.         for (int i = 0; i < X; i++)
  89.         {
  90.                 for (int j = 0; j < Y; j++)
  91.                 {
  92.                         printf("%3d", chess[i][j]);
  93.                 }
  94.                 cout << endl;
  95.         }
  96.         cout << endl;
  97. }

  98. //搜素下一步
  99. int TravelChess(int x, int y, int tag)
  100. {
  101.         int count = 0, flag = 0;
  102.         int x1 = x, y1 = y;
  103.         chess[x1][y1] = tag;
  104.         if (X*Y == tag)
  105.         {
  106.                 print();//打印棋盘
  107.                 return 1;
  108.         }

  109.         while (flag!=1&&count <= 7)
  110.         {
  111.                 flag = IsHaveNext(&x1, &y1, count);
  112.                 count++;
  113.         }

  114.         while (flag)
  115.         {
  116.                 if (TravelChess(x1, y1, tag+1))
  117.                 {
  118.                         return 1;
  119.                 }
  120.                 x1 = x, y1 = y;
  121.                 flag = 0;
  122.                 while (flag != 1 && count <= 7)
  123.                 {
  124.                         flag = IsHaveNext(&x1, &y1, count);
  125.                         count++;
  126.                 }
  127.         }

  128.         if (flag == 0)
  129.         {
  130.                 chess[x][y] = 0;

  131.         }
  132.         return 0;
  133. }

  134. int main()
  135. {
  136.         clock_t s, e;
  137.         int x, y;
  138.         cout << "input the initial position:" << endl;
  139.         cin >> x;
  140.         cin >> y;
  141.         s = clock();
  142.         if (!TravelChess(x, y, 1))
  143.         {
  144.                 cout << "Failed !" << endl;
  145.         }

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

  148.         system("PAUSE");
  149. }
复制代码

评分

参与人数 1鱼币 +2 收起 理由
小甲鱼 + 2

查看全部评分

本帖被以下淘专辑推荐:

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 21:51

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表