解救小哈——深度优先搜索

题目描述：

有一天，小哈一个人去玩迷宫。但是方向感很不好的小哈很快就迷路了。小哼得知后便立即去解救无助的小哈。小哼当然是有备而来，已经弄清楚了迷宫的地图，现在小哼要以最快的速度去解救小哈。问题就此开始了……

迷宫由m行n列的单元格组成的（m和n都小于50），每个单元格要么是空地要么是障碍物，你的任务是帮小哼找到一条从迷宫的起点通往小哈所在位置的最短路径。

样例输入：

5 4
0 0 1 0
0 0 0 0
0 0 1 0
0 1 0 0
0 0 0 1
1 1 4 3

题解：

#include<stdio.h>
int n, m, p, q, min = 99999999;
int a[51][51], book[51][51];

void dfs(int x, int y, int step){
                    //向右走  向下   向左    向上
    int next[4][2] = {{0, 1},{1, 0},{0, -1},{-1 ,0}};

    int tx, ty, k;
    //判断是否到达小哈位置
    if (x == p && y == q){
        //更新最小值
        if (step < min){
            min = step;
        }return;
    }
    //枚举4种走法
    for (k = 0 ; k < 4 ; k ++){
        //计算下一个点的坐标
        tx = x + next[k][0];
        ty = y + next[k][1];

        //判断是否越界
        if (tx < 1 || tx > n || ty < 1 || ty > m)
            continue;
        //判断该点是否为障碍物或者已经在路径中
        if (a[tx][ty] == 0 && book[tx][ty] == 0){
            book[tx][ty] = 1; // 标记这个点
            dfs(tx, ty, step+1); //开始尝试下一个点
            book[tx][ty] = 0; //尝试结束，取消这个点的标记
        }
    }
    return ;
}

int main(){
    int i, j, startx, starty;
    //读入n和m， n为行，m为列;
    scanf("%d %d", &n, &m);
    //读入迷宫
    for (i = 1 ; i <= n ; i ++){
        for (j = 1; j <= m; j ++){
            scanf("%d",&a[i][j]);
        }
    }
    //读入起点和终点坐标
    scanf("%d %d %d %d",&startx, &starty, &p ,&q);

    //从起点开始搜索
    book[startx][starty] = 1; //标记起点已经在路径中，防止后面重复走
    //第一个参数是起点的x坐标，第二个参数是起点的y坐标，第三个参数是初始步数为0
    dfs(startx, starty, 0);
    //输出最短步数
    printf("%d\n",min);
    return 0;
}

运行结果：