hdu 1010 （DFS+剪枝）

BFS，DFS，都可以，只要拍注意剪枝就可以了。

注意題目中要求只能在T秒到D。

題目中有坑。測試數據中每行有多余的空格。。。就這一點卡了一個晚上

[cpp]
#include"stdio.h"  
#include"string.h"  
#include"math.h"  
#define zz 10  
 
int mark[zz][zz]; 
char map[zz][zz]; 
int n,m,t,s,e,ss,ee,f; 
int dir[4][2]={1,0,0,1,-1,0,0,-1}; 
 
void dfs(int x,int y,int t) 
{ 
    int i,dis; 
    int xx,yy; 
    if(x==ss&&y==ee) 
    { 
        if(t==0)f=1; 
        return ; 
    } 
    if(f==1)return ; 
    dis=abs(x-ss)+abs(y-ee); 
    if(dis>t||(t-dis)%2!=0)return ; 
    for(i=0;i<4;i++) 
    { 
        xx=x+dir[i][0]; 
        yy=y+dir[i][1]; 
        if(xx>=0&&xx<n&&yy>=0&&yy<m&&!mark[xx][yy]&&map[xx][yy]!='X') 
        { 
            mark[xx][yy]=1; 
            dfs(xx,yy,t-1); 
            mark[xx][yy]=0; 
        } 
    } 
} 
 
int main() 
{ 
    int i,j,k; 
    while(scanf("%d %d %d%*c",&n,&m,&t)!=-1&&(n+m+t)) 
    { 
        k=0; 
        memset(map,0,sizeof(map)); 
        memset(mark,0,sizeof(mark)); 
        for(i=0;i<n;i++) 
        { 
            for(j=0;j<m;j++) 
            { 
                scanf("%c",&map[i][j]); 
                if(map[i][j]=='S') 
                    s=i,e=j; 
                if(map[i][j]=='D') 
                    ss=i,ee=j,k++; 
                if(map[i][j]=='.') 
                    k++; 
            } 
            scanf("%*c"); 
        } 
         
        if(k<t) 
        { 
            printf("NO\n"); 
            continue; 
        } 
        f=0; 
        mark[s][e]=1; 
        dfs(s,e,t); 
        if(f==1)printf("YES\n"); 
        else printf("NO\n"); 
    } 
    return 0; 
}