题目ID：3342 骨头的诱惑
时间限制: 500ms
空间限制: 32768kB
题目描述:
在一个迷宫里面有一只小狗发现了一根骨头，现在他准备逃出迷宫，迷宫中只有一个地方有门可以出去，而且这个门只会在T秒的时候打开，开了之后下一时刻就会关闭。每移动一步要花费1秒，规定不能停留在某一个位置上，即走到一个位置要立刻前往下一个位置。每个位置不能重复走。假设小狗很聪明，它能成功逃出迷宫么？
输入格式：
第一行输入三个整数 n, m , T,表示迷宫的尺寸以及门打开的时间
接下来 n 行,每行 m 个字符，表示迷宫中每一个位置上的信息。
‘X’: 表示墙，不能进入
‘S’: 小狗现在的位置
‘D’: 门
‘.’: 空地
输出格式：
根据能否成功逃离，输出
“YES”或者“NO”
样例输入1：
4 4 5
S.X.
..X.
..XD
....
样例输出1：
NO
样例输入2：
3 4 5
S.X.
..X.
...D
样例输出2：
YES
约定：
1 < n, m < 7, 0 < T < 50
做题思路
本题涉及 dfs算法. 算法传送门
输入时，找到S点和D点，标记为起始坐标和结束坐标。
for(int i = 1;i <= n;++ i)
{
for(int j = 1;j <= m;++ j)
{
cin >> mp[i][j];
if(mp[i][j] == 'S')
{
sx = i;
sy = j;
vis[sx][sy] = true;
}
if(mp[i][j] == 'D')
{
ex = i;
ey = j;
}
}
}
搜索时让小狗不停上下左右走，走到时间为T时，判断坐标是否为D，是的话输出YES，结束程序，最后输出NO。
if(dep == t)
{
if(x == ex && y == ey)
{
cout << "YES";
exit(0);
}
return;
}
tip: （注意搜完一个点要回溯）
有一个问题是，要用vis数组，搜的时候要判断是否走过，坐标点是否为墙，判断是否出界。
void dfs(int dep, int x, int y)
{
if(dep == t)
{
if(x == ex && y == ey)
{
cout << "YES";
exit(0);
}
return;
}
for(int i = 0;i < 4;++ i)
{
int xx = x + dx[i];
int yy = y + dy[i];
if(xx > n || yy > m || xx < 1 || yy < 1 || mp[xx][yy] == 'X' || vis[xx][yy]) continue;
vis[xx][yy] = true;
dfs(dep + 1, xx, yy);
vis[xx][yy] = false;
}
}