ZOJ 2110 Tempter of the Bone（DFS）

点我看题目

题意 ： 一个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  ;

}