问题 L: 肉骨头的诱惑
题目描述
小狗在一个古老的迷宫中发现了一根骨头，这使他非常着迷。但是，当他捡起它时，迷宫开始摇晃，小狗可以感觉到地面下沉。他意识到骨头是一个陷阱，他拼命试图摆脱这个迷宫。迷宫是一个矩形，大小为N×M。迷宫中有一扇门。刚开始时，门是关闭的，它将在第T秒打开一小段时间（少于1秒）。因此，小狗必须在第T秒精确到达门。每秒钟，他可以将一个块移动到上，下，左和右相邻的块之一。一旦他进入一个块，该块的地面将开始下沉并在下一秒消失。他不能在一个块停留超过一秒钟，也不能走到曾经走过的块区上。可怜的小狗可以生存吗？请帮助他。
输入
输入包含多个测试用例。每个测试用例的第一行包含三个整数N，M和T（1 <N，M <= 7； 0 <T <50），表示迷宫的大小和门打开的时间，分别。接下来的N行给出迷宫的布局，每行包含M个字符。角色是以下字符之一：'X'：小狗无法进入的墙块；'S'：小狗的起点；'D'：门；或“.”：空白块。输入以三个0终止。该测试用例将不被处理。
输出
对于每个测试用例，如果小狗可以存活，则在一行中输出“YES”，否则输出“NO”。
样例输入
4 4 5 S.X. ..X. ..XD .... 3 4 5 S.X. ..X. ...D 0 0 0
样例输出
NO YES
这道题我暴交了15次，结果都是tle50分，各位大佬帮忙看看
代码：
#include <bits/stdc++.h>
#define MAXN 10
using namespace std;
int n,m,t;
int flag;
char str[MAXN][MAXN];
int zb[4][2] = {{0,-1},{0,1},{-1,0},{1,0}};
void dfs(int bx,int by,int dx,int dy,int tim)
{
if(bx>n || by>m || bx<=0 || by<=0) return;
if(bx == dx && by == dy && tim == t)
{
flag=1;
return;
}
for(int i=0 ; i<4 ; ++i)
{
if(str[bx+zb[i][0]][by+zb[i][1]]!='X')
{
str[bx+zb[i][0]][by+zb[i][1]] = 'X';
dfs(bx+zb[i][0],by+zb[i][1],dx,dy,tim+1);
if(flag) return;
str[bx+zb[i][0]][by+zb[i][1]] = '.';
}
}
return;
}
int main()
{
int dx,dy,bx,by;
while(scanf("%d%d%d", &n, &m, &t))
{
int wall_sum = 0;
getchar();
if(n == 0 && m == 0 && t == 0) break;
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j <= m; ++j)
{
scanf("%c", &str[i][j]);
if(str[i][j] == 'S'){bx = i;by = j;}
else if(str[i][j] == 'D'){dx = i;dy = j;}
else if(str[i][j] == 'X') wall_sum++;
}
getchar();
}
flag=0;
if(n*m <= t+wall_sum){printf("NO\n");continue;}
str[bx][by]='X';
dfs(bx,by,dx,dy,0);
if(flag) printf("YES\n");
else printf("NO\n");
}
}