点我看题目
题意 ： 一个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[9][9] ; int mp[9][9]; int sx,sy ; int ex,ey ; bool flag ; int ans; int dire[4][2] = {{0,-1},{0,1},{1,0},{-1,0}} ;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 < 0 || temp%2) return ;for(int i = 0 ; i < 4 ; i++){int xx = x+dire[i][0] ;int yy = y+dire[i][1] ;if(xx >= 0 && xx < N && yy >= 0 && yy < M && mp[xx][yy]){mp[xx][yy] = 0 ;DFS(xx,yy,t+1) ;if(flag) return ;mp[xx][yy] = 1 ;}} } int main() {while(scanf("%d %d %d",&N,&M,&T)!=EOF){getchar();if(N == 0 && M == 0 && T == 0) break ;memset(mp,0,sizeof(mp)) ;flag = false ;int wall = 0 ;for(int i = 0 ; i < N ; i++){scanf("%s",mapp[i]);for(int j = 0 ; 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] = 1 ;}else if(mapp[i][j] == '.')mp[i][j] = 1 ;else wall ++ ;}}if(N*M-wall <= T){printf("NO\n") ;continue ;}mp[sx][sy] = 0 ;DFS(sx,sy,0) ;if(flag)printf("YES\n") ;else printf("NO\n") ;}return 0 ; }
