HDOJnbsp;nbsp;1010nbsp;nbsp;nbsp;Tempternbsp;ofnbsp;thenbsp;Bone

题目：http://acm.hdu.edu.cn/showproblem.php?pid=1010

#include <stdio.h>
#include <math.h>
char  map[10][10];   //记住数组不能为7
int n,m,t;     
int  di,dj;     //门的位置
bool escape;     //判断是否成功的标志
int dir[4][2]={{0,-1},{0,1},{1,0},{-1,0}};       //表示上下左右四个方向
void dfs(int si,int sj,int cut)
{
    int i,temp;
    if(si>n||sj>m||si<=0||sj<=0)
        return;
    if(si==di&&sj==dj&&cut==t)
    {
        escape=1;
        return;
    }
    temp=(t-cut)-fabs(si-di)-fabs(sj-dj);  //进行剪枝
    if(temp<0||temp%2)
        return ;
    for(i=0;i<4;i++)
    {
        if(map[si+dir[i][0]][sj+dir[i][1]]!='X')
        {
            map[si+dir[i][0]][sj+dir[i][1]]='X';
            dfs(si+dir[i][0],sj+dir[i][1],cut+1);
            if(escape)
                return;
            map[si+dir[i][0]][sj+dir[i][1]]='.';
        }
    }
    return;
}
int main()
{
  int i,j;
  int si,sj;
  char p;
  while(1)
  {
      scanf("%d%d%d",&n,&m,&t);
      if(!n&&!m&&!t)
        break;
      int wall=0;
      p=getchar();
      for(i=1;i<=n;i++)
      {
         for(j=1;j<=m;j++)
         {
            scanf("%c",&map[i][j]);
            if(map[i][j]=='S')
                si=i,sj=j;
            else if(map[i][j]=='D')
                di=i,dj=j;
            else if(map[i][j]=='X')
                wall++;
          }
          p=getchar();

      }
      if(n*m-wall<=t)   //进行剪枝
       {
           printf("NO\n");
           continue;
       }
       escape=0;
       map[si][sj]='X';
       dfs(si,sj,0);
       if(escape)
          printf("YES\n");
       else
          printf("NO\n");
  }
  return 0;
}