noj电子老鼠走迷宫（深搜dfs）超时错误

1042.电子老鼠闯迷宫

时限：1000ms 内存限制：10000K  总时限：3000ms

描述

有一只电子老鼠被困在如下图所示的迷宫中。这是一个12*12单元的正方形迷宫，黑色部分表示建筑物，白色部分是路。电子老鼠可以在路上向上、下、左、右行走，每一步走一个格子。现给定一个起点S和一个终点T，求出电子老鼠最少要几步从起点走到终点。

 

输入

本题包含一个测例。在测例的第一行有四个由空格分隔的整数，分别表示起点的坐标S（x.y）和终点的坐标T（x,y）。从第二行开始的12行中，每行有12个字符，描述迷宫的情况，其中'X'表示建筑物，'.'表示路.

 

输出

输出一个整数，即电子老鼠走出迷宫至少需要的步数。

 

输入样例

2 9 11 8
XXXXXXXXXXXX
X......X.XXX
X.X.XX.....X
X.X.XX.XXX.X
X.X.....X..X
X.XXXXXXXXXX
X...X.X....X
X.XXX...XXXX
X.....X....X
XXX.XXXX.X.X
XXXXXXX..XXX
XXXXXXXXXXXX

 

输出样例

28

#include <stdio.h>

#include <string.h>

int n=,m=,p,q,min = ;

int book[][];

char a[][];

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

{

    int next[][] = {{,},{,},{,-},{-,}};

    int tx,ty,k;

    if (x==p&&y==q)//判断是否到达位置

    {

        if(step<min)

            min = step;

        return;

    }

    for (k = ;k <= ;k++)//枚举四种走法

    {

        tx = x + next[k][];

        ty = y + next[k][];

        if (tx<||tx>n||ty<||ty>m)//判断是否越界

        {

            continue;

        }

        if (a[tx][ty]=='.'&&book[tx][ty]==)//判断是否为障碍物和是否在路径中

        {

            book[tx][ty] = ;

            dfs(tx,ty,step+);

            book[tx][ty]=;

        }

    }

    return;

}

int main()

{

    int i,startx,starty;

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

    getchar();

    for(i=;i<=n;i++)

          gets(a[i]);

    book[startx][starty] = ;

    dfs(startx,starty,);

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

    return ;

}