解救小哈（深度搜索）

本题可以用深度搜索，也可以用广度搜索，相对来说，广度搜索更加简洁，但是为了学习深度搜索，故本题采用深度搜索。

思路：依然是使用递归，一步一步向前试探，试探后再回溯，最后比较结果，即可得出答案。

代码如下：

#include<stdio.h>
#define MAX_N 100
#define MAX_M 100
int a[MAX_N][MAX_M];
int p,q,n,m;
int min=MAX_N+MAX_M;
void dfs(int x,int y,int step); 
int main(void)
{    
    int i,j;   // n行  m列 
    int startx,starty;  //  (startx,starty)为起点 ; (p,q)为终点；
    
    /*数据的输入*/
    scanf("%d%d",&n,&m);
    for(i=0;i<n;i++)
    {
        for(j=0;j<m;j++)
        {
            scanf("%d",&a[i][j]);
        }
    }
    scanf("%d%d%d%d",&startx,&starty,&p,&q);
    /*数据的处理*/
    
    startx=startx-1;
    starty=starty-1;
    p=p-1;
    q=q-1;  
    /*因为输入数据是从 (1,1) 开始计数，而数组是从 (0,0) 开始计数。所以此处都要减去 1 */ 
    dfs(startx,starty,0);
    printf("%d
",min);
    
    return 0;    
} 
void dfs(int x,int y,int step)
{
//    printf("%d
",step);  //测试所走的步数 
    if(x==p&&y==q)
    {
        if(min>step)
        {
            min=step;
        }
        return ;
    }    
    if(a[x][y]==1)
    {
        return ;
    }
    if(x+1<n)
    {
        a[x][y]=1; 
        dfs(x+1,y,step+1);
        a[x][y]=0; 
    }
    if(x-1>0)
    {
        a[x][y]=1; 
        dfs(x-1,y,step+1);
        a[x][y]=0; 
    }
    if(y+1<m)
    {
        a[x][y]=1; 
        dfs(x,y+1,step+1);
        a[x][y]=0; 
    }
    if(x-1<0)
    {
        a[x][y]=1; 
        dfs(x,y-1,step+1);
        a[x][y]=0; 
    }
}

再附上一些测试数据：

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

3 2
0 1
0 0
0 0
1 1 3 2

5 4
0 0 1 0
0 0 0 0
0 0 1 0
0 1 1 0
0 0 0 0
1 1 5 2

此代码没有使用标记数组，也可以使用标记数组来解答此题。