深搜算法实例：老鼠走迷宫（一）

这个是简单的深搜，应该输入深搜中抛砖型的，联系下代码，回顾一下深搜的思想。
本题的要求是，在开始点(1,1)和终点(5,5)放一只老鼠，让老鼠找到一条路径走出去（暂时不考虑最短路径），找到后输出路径。
最简单的想法就是对于上下左右四个进行刨根型的搜索，找到就返回输出，进入死胡同了就原路返回，找最近的有其他路径的点，继续搜索，知道找出为止。
下面是代码部分。

#include <stdio.h>
#include <stdlib.h>
#define SUCCESS 1
#define FAIL 0

int visit(int,int);
void map();
void route();

int maze[7][7]={ {2,2,2,2,2,2,2}, {2,0,0,0,0,0,2}, {2,0,0,0,2,0,2}, {2,0,0,0,0,2,2}, {2,2,0,2,0,2,2}, {2,0,0,0,0,0,2}, {2,2,2,2,2,2,2}};

int start_i=1,start_j=1;
int end_i=5,end_j=5;
int flag=FAIL;

int main(void)
{ map(); route(); return 0;
}

void map()
{ int i,j; printf("显示迷宫：\n"); for(i=0;i<7;i++) { for(j=0;j<7;j++) if(maze[i][j]==2) printf("*"); else printf(" "); printf("\n"); }
}

void route()
{ int i,j; if(visit(start_i,start_j)==FAIL) printf("\n此路不同！换个地图！"); else{ printf("\n显示路径：\n"); for(i=0;i<7;i++) { for(j=0;j<7;j++) if(maze[i][j]==2) printf("*"); else if(maze[i][j]==1) printf("@"); else printf(" "); printf("\n"); } }
}

int visit(int i,int j)
{ maze[i][j]=1; if(i==end_i && j==end_j) flag=SUCCESS; if(flag==FAIL && maze[i][j+1]==0) visit(i,j+1); if(flag==FAIL && maze[i+1][j]==0) visit(i+1,j); if(flag==FAIL && maze[i-1][j]==0) visit(i-1,j); if(flag==FAIL && maze[i][j-1]==0) visit(i,j-1); if(flag==FAIL) maze[i][j]=0; return flag;
}
  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
  
62
  
63
  
64
  
65
  
66
  
67
  
68
  
69
  
70
  
71
  
72
  
73
  
74
  
75
  
76
  
77
  
78
  
79
  
80
  
81
  
82
  
83
 

从上面的分析中我们只看visit()函数
我们用了0,1,2三个数表示地图某一点的状态：

1.0表示无障碍
2.1表示通路中的一点
3.2表示障碍

并用一个数组保存
我们看到，在visit()函数中进行了函数自身调用（可以看做是递归），这里是先朝着右边搜索，然后是上，下，左，如果还能往下走就接着往下走，走到不能再走为止。如果是死胡同，则就退到上一节点（这就是回溯了，在代码中的maze[i][j]=0表现），在新的节点继续试探，看有没有能一直走到终点的路线，一旦找到就马上返回（在flag=SUCCESS这里说明，找到一条就不再找别的路线了），没有的话就接着深搜，直到遍历完所有的节点发现到底有没有通路存在。
总的来说这个作为深搜的入门挺不错，没有难度，还有点小趣，同时还能再回顾下递归的思想

文章来源: chenhx.blog.csdn.net，作者：谙忆，版权归原作者所有，如需转载，请联系作者。

原文链接：chenhx.blog.csdn.net/article/details/47858321