啊哈算法—解救小哈深度优先搜索

解救小哈

小哈在一个（m * n)大小的迷宫（0 ⇐ m, n ⇐ 50）里迷路了。在迷宫中，每个单元格要么是空地，要么是障碍物。现在要找到从起点到小哈位置的最短步数。

思路：

使用递归一步一步向前试探，试探成功则步数加一，返回后向另一个方向试探，到达终点后比较最小步数。

源码：

1.  
   #include<stdio.h>
2.  
    
3.  
   int n, m, p, q, min = _CRT_INT_MAX;
4.  
   int a[51][51], book[51][51];
5.  
    
6.  
   void dfs(x, y, step);
7.  
    
8.  
   void dfs(x, y, step) {
9.  
   int next[4][2] = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} }; //控制下一步走的方向
10.  
    int tx, ty; //下一步坐标
11.  
    int k;
12.  
     
13.  
    if (x == p && y == q) { //到达终点
14.  
    if (step < min) {
15.  
    min = step; //更新最小值
16.  
    }
17.  
    return;
18.  
    }
19.  
     
20.  
    for (k = 0; k < 3; k ) { //循环尝试下一步
21.  
    tx = x next[k][0];
22.  
    ty = y next[k][1];
23.  
    if (tx < 1 || tx > n || ty < 1 || ty > m) { //判断是否出界
24.  
    continue;
25.  
    }
26.  
    if (a[tx][ty] == 0 && book[tx][ty] == 0) { //判断是否为障碍物或已走过
27.  
    book[tx][ty] = 1; //标记此格已走过
28.  
    dfs(tx, ty, step 1);
29.  
    book[tx][ty] = 0; //取消尝试
30.  
    }
31.  
    }
32.  
    return;
33.  
    }
34.  
     
35.  
    int main() {
36.  
    int i, j;
37.  
    int startx, starty;
38.  
     
39.  
    printf("请输入迷宫大小\n");
40.  
    scanf("%d %d", &n, &m); //输入迷宫大小
41.  
     
42.  
    printf("请输入迷宫\n");
43.  
    for (i = 1; i <= n; i ) { //输入迷宫
44.  
    for (j = 1; j <= m; j ) {
45.  
    scanf("%d", &a[i][j]);
46.  
    }
47.  
    }
48.  
     
49.  
    printf("请输入终点：");
50.  
    scanf("%d %d", &p, &q); //输入终点；
51.  
     
52.  
    printf("请输入起点：");
53.  
    scanf("%d %d", &startx, &starty);
54.  
     
55.  
    dfs(startx, starty, 0);
56.  
     
57.  
    printf("最小路径：%d", min);
58.  
     
59.  
    return 0;
60.  
    }

这篇好文章是转载于：学新通技术网