Chinaunix

标题: linux C一站式学习 [打印本页]
作者: bellszhu    时间: 2013-04-21 16:42
标题: linux C一站式学习
这本书的12.3节，例子12.3 用深度优先搜索解迷宫问题。。
个人觉得不是深度优先啊，而是广度优先呀。。请问是不是？
程序如下：
  1. #include <stdio.h>

  3. #define MAX_ROW 5
  4. #define MAX_COL 5

  6. struct point {int row, col;} stack[512];
  7. int top = 0;

  9. void push(struct point p) {
  10.         stack[top] = p;
  11.         top++;
  12. }

  14. struct point pop(void) {
  15.         top--;
  16.         return stack[top];
  17. }

  19. int is_empty(void) {
  20.         return top == 0;
  21. }

  23. int maze[MAX_ROW][MAX_COL] = {
  24.         0, 1, 0, 0, 0,
  25.         0, 1, 0, 0, 0,
  26.         0, 0, 0, 0, 0,
  27.         0, 1, 1, 1, 0,
  28.         0, 0, 0, 1, 0,
  29.        
  30. };

  32. void print_maze(void) {
  33.         int i, j;
  34.         for (i = 0; i < MAX_ROW; i++) {
  35.                 for (j = 0; j < MAX_COL; j++) {
  36.                         printf("%d ", maze[i][j]);
  37.                 }
  38.                 putchar('\n');
  39.         }
  40. }

  42. struct point predecessor[MAX_ROW][MAX_COL] = {
  43.         {{-1, -1}, {-1, -1}, {-1, -1}, {-1, -1}, {-1, -1}},
  44.         {{-1, -1}, {-1, -1}, {-1, -1}, {-1, -1}, {-1, -1}},
  45.         {{-1, -1}, {-1, -1}, {-1, -1}, {-1, -1}, {-1, -1}},
  46.         {{-1, -1}, {-1, -1}, {-1, -1}, {-1, -1}, {-1, -1}},
  47.         {{-1, -1}, {-1, -1}, {-1, -1}, {-1, -1}, {-1, -1}},
  48. };

  50. void visit(int row, int col, struct point pre) {
  51.         struct point visit_point = {row, col};
  52.         maze[row][col] = 2;
  53.         predecessor[row][col] = pre;
  54.         push(visit_point);
  55. }

  57. int main(void) {
  58.         struct point p = {0, 0};
  59.         maze[p.row][p.col] = 2;
  60.         push(p);

  62.         while(!is_empty()) {
  63.                 p = pop();
  64.                 if (p.row == MAX_ROW - 1 && p.col == MAX_COL - 1) {
  65.                         break;
  66.                 }
  67.                 if (p.row + 1 < MAX_ROW && maze[p.row + 1][p.col] == 0) {
  68.                         visit(p.row + 1, p.col, p);
  69.                 }
  70.                 if (p.col + 1 < MAX_COL && maze[p.row][p.col + 1] == 0) {
  71.                         visit(p.row, p.col + 1, p);
  72.                 }
  73.                 if (p.col - 1 >= 0 && maze[p.row][p.col - 1] == 0) {
  74.                         visit(p.row, p.col - 1, p);
  75.                 }
  76.                 if (p.row - 1 >= 0 && maze[p.row - 1][p.col] == 0) {
  77.                         visit(p.row - 1, p.col, p);
  78.                 }
  79.                 print_maze();
  80.         }

  82.         if (p.row == MAX_ROW - 1 && p.col == MAX_COL - 1) {
  83.                 printf("(%d, %d) \n", p.row, p.col);
  84.                 while (predecessor[p.row][p.col].row != -1) {
  85.                         p = predecessor[p.row][p.col];
  86.                         printf("(%d, %d)\n", p.row, p.col);
  87.                 }
  88.         } else {
  89.                 printf("No path!\n");
  90.         }

  92.         return 0;
  93. }
复制代码




欢迎光临 Chinaunix (http://bbs.chinaunix.net/) Powered by Discuz! X3.2