题目描述

现有一块迷宫，小哈要从起始位置出发，去解救被困的校长。首先我们可以用一个二维数组来存储这个迷宫，在存储时1表示障碍物，0表示空地。求小哈解救校长的最短路径。

解题思路

这题可以用深度优先搜索算法，来解决。为了方便设小哈的搜索方向为顺时针，即沿右，下，左，上的方向进行搜索。在走的过程中若离开迷宫，则换一个方向，若没有则沿，

此方向走，将走过的点标记为1，表示已走过，若碰到障碍物，或走到校长的位置，则返回到标记为1的最近的位置并将其标记为0，继续寻找。

代码如下

#include<stdio.h>

int book[10][10],min=1000,p,q,k,a[10][10],k1;

void dfs(int x,int y,int step)

{

    int i,tx,ty;

    int next[4][2]={

{1,0},{0,1},{-1,0},{0,-1}};

    if(x==p&&y==q)

    {

        if(step<min)

        min=step;

        return;

    }

    for(i=0;i<4;i++)

    {

        tx=x+next[i][0];

        ty=y+next[i][1];

        if(tx>k1||ty>k||tx<1||ty<1)          //注意是tx>k1,ty>k而不是tx>k,ty>k1

        continue;

        if(book[tx][ty]==0&&a[tx][ty]==0)

        {

            book[tx][ty]=1;

            dfs(tx,ty,step+1);

            book[tx][ty]=0;

        }

    }

    return;

}

int main()

{

    int i,j,startx,starty;

    scanf("%d%d",&k,&k1);

    for(i=1;i<=k;i++)

    {

        for(j=1;j<=k1;j++)

        scanf("%d",&a[i][j]);

    }

    scanf("%d%d%d%d",&startx,&starty,&p,&q);

    book[1][1]=1;

    dfs(startx,starty,0);

    printf("%d\n",min);

    return 0;

}

深度优先搜索算法的适用问题

1.迷宫问题

以后会继续增加