题意 : 一个N×M的迷宫,D是门的位置,门会在第T秒开启,而开启时间小于1秒,问能否在T秒的时候到达门的位置,如果能输出YES,否则NO。
思路 :DFS一下就可以,不过要注意下一终止条件再判断一下时间,还有因为题目中要求走过的路要变成墙,所以每次走的时候要注意一下把路变成墙,但是如果你不走这条路了,要记得变回来。还有这个题必须剪枝,否则超时超到疯啊,DFS函数中那个剪枝不怎么好想,T-t代表的是在当前位置还需要T-t步路。而fabs(ex-x)+fabs(ey-y)指的是当前位置离终点最短还有着些步数,如果两者之差不小于0的话,T-t应该等于fabs(ex-x)+fabs(ey-y)+s,这个s,如果再扩展的话增加的长宽必定是偶数,所以奇数是不可达的
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <string.h> using namespace std ; int N,M,T ;
char mapp[][] ;
int mp[][];
int sx,sy ;
int ex,ey ;
bool flag ;
int ans;
int dire[][] = {{,-},{,},{,},{-,}} ; void DFS(int x,int y,int t)
{
if(x == ex && y == ey&&t==T)
{
flag = true ;
return ;
}
int temp = (T-t)-fabs(ex-x)-fabs(ey-y) ;
if(temp < || temp%) return ;
for(int i = ; i < ; i++)
{
int xx = x+dire[i][] ;
int yy = y+dire[i][] ;
if(xx >= && xx < N && yy >= && yy < M && mp[xx][yy])
{
mp[xx][yy] = ;
DFS(xx,yy,t+) ;
if(flag) return ;
mp[xx][yy] = ;
}
}
}
int main()
{
while(scanf("%d %d %d",&N,&M,&T)!=EOF)
{
getchar();
if(N == && M == && T == ) break ;
memset(mp,,sizeof(mp)) ;
flag = false ;
int wall = ;
for(int i = ; i < N ; i++)
{
scanf("%s",mapp[i]);
for(int j = ; j < M ; j++)
{
if(mapp[i][j] == 'S')
sx = i ,sy = j ;
else if(mapp[i][j] == 'D')
{
ex = i,ey = j ;
mp[i][j] = ;
}
else if(mapp[i][j] == '.')
mp[i][j] = ;
else wall ++ ;
}
}
if(N*M-wall <= T)
{
printf("NO\n") ;
continue ;
}
mp[sx][sy] = ;
DFS(sx,sy,) ;
if(flag)
printf("YES\n") ;
else printf("NO\n") ;
}
return ;
}