[图论]-有一个东西叫做DFS(hellokitty抓米奇)

啊哈磊

输入样例：
4 5
0 0 0 0 0
0 1 0 0 0
0 0 1 1 0
1 0 0 0 0
2 5
4 3
注：第一行两个数分别表示迷宫的长和宽
接下来是具体的迷宫，1是墙，0是可以走的地方
在接下来是hellokitty的坐在坐标
在接下来是米奇的坐标
输出样例：
4

代码：

[code=Cpp width=740px]#include <stdio.h>
#define MAX 99999999
int a[51][51];
int book[51][51];
int n,m,sx,sy,ex,ey;
int min=MAX;

void dfs(int x ,int y,int s)
{
    //到达目标
    if(x==ex && y==ey)
    {
        //最小值更新
        if(s<=min)
            min=s;
        //这个地方一要记得返回
        return;
    }
    //边界剪枝
    if( x < 1 || x > n || y < 1 || y > m)
        return ; //每个剪枝一定要返回
   
    //判断是否是墙  以及 是否已经走过
    if(a[x][y]==1 || book[x][y]==1)
        return ;//每个剪枝一定要返回
   
   
    book[x][y]=1;//开始走,标记一下，这里标记一下就代表走完了，有的题目还需要其他的操作
   
    //接下来尝试朝四个方向走
    dfs(x,y+1,s+1);
    dfs(x,y-1,s+1);
    dfs(x+1,y,s+1);
    dfs(x-1,y,s+1);
   
    //将刚刚走的标记为没有走，也就是还原
    book[x][y]=0;
   
    return ;
}

int main()
{
    int i,j;
    freopen("dfs.in","r",stdin);
    freopen("dfs.out","w",stdout);
   
    scanf("%d %d",&n,&m);
    for( i = 1; i <= n; i++ )
        for( j = 1; j <= m; j++)
            scanf("%d",&a[j]);
    scanf("%d %d %d %d",&sx,&sy,&ex,&ey);
   
    //从猫的起点开始深度搜素
    dfs(sx,sy,0);
   
    if(min==MAX)
        printf("-1");
    else
        printf("%d",min);
    return 0;
}
</stdio.h>[/code]