1 /*
   2 hdu 1010  DFS+剪枝
   3 ymc 2008/09/16
   4 
   5 题目大意：
   6 在n×m的地图上，一直从位置S出发，是否能恰好在t时刻到D。
   7 X代表墙，.代表空地。所有空地只能走一次。
   8 分析与解题思路：
   9 从S出发，DFS搜索D。但是容易TLE
  10 剪枝条件：
  11 1.奇偶性：给地图上黑白色，相邻的上不同颜色。没走一步颜色变化一次。
  12 所以S与D的坐标距离（x之差＋y之差）与t的奇偶性不一致是，必定无解。
  13 2.所有能走的格子个数如果小于t，必定无解。
  14 3.DFS(x,y,k)，为当前位置为(x,y),时间为k时的状态。
  15 则(x,y)与D的坐标距离大于t-k或者奇偶性步一致时，剪枝。
  16 */
  17 #include <iostream>
  18 #include <queue>
  19 #include <cmath>
  20 using namespace std;
  21 const int N=10;
  22 char map[N][N];
  23 int n,m,t;
  24 int step[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
  25 int sx,sy,ex,ey;
  26 bool ans;
  27 int num;
  28 int dist[N][N];
  29 void Init()
  30 {
  31     num=0;
  32     for(int i=0;i<n;i++)
  33         for(int j=0;j<m;j++)
  34         {
  35             if(map[i][j]=='S')
  36             {
  37                 sx=i;sy=j;
  38                 map[i][j]='.';
  39             }
  40             else if(map[i][j]=='D')
  41             {
  42                 ex=i;ey=j;
  43                 map[i][j]='.';
  44             }
  45             else if(map[i][j]=='X')
  46                 num++;
  47         }
  48     num=n*m-num-1;
  49     ans=false;
  50 }
  51 
  52 void DFS(int x,int y,int k)
  53 {
  54     if(k>t) return;
  55     if(k==t&&x==ex&&y==ey)
  56     {
  57         ans=true;
  58         return;
  59     }
  60     if(ans==true)
  61         return;
  62     int tmp=t-k-abs(ex-x)-abs(ey-y);
  63     if(tmp<0||tmp%2==1) //剪枝，关键，距离与奇偶性
  64         return;
  65     int x1,y1;
  66     for(int i=0;i<4;i++)
  67     {
  68         x1=x+step[i][0];
  69         y1=y+step[i][1];
  70         if(x1<0||x1>=n||y1<0||y1>=m||map[x1][y1]=='X')
  71             continue;
  72         map[x][y]='X';
  73         DFS(x1,y1,k+1);
  74         map[x][y]='.';
  75 
  76     }
  77 }
  78 void Solve()
  79 {
  80     int dx,dy;
  81     dx=abs(sx-ex);
  82     dy=abs(sy-ey);
  83     if((dx+dy-t)%2==1)
  84         return;
  85     if(num<t)
  86         return;
  87     DFS(sx,sy,0);
  88 }
  89 int main()
  90 {
  91     while(scanf("%d %d %d",&n,&m,&t))
  92     {
  93         if(n==0&&m==0&&t==0) break;
  94         memset(map,'X',sizeof(map));
  95         for(int i=0;i<n;i++)
  96             scanf("%s",map[i]);
  97         Init();
  98         Solve();
  99         if(ans==true)
 100             printf("YES\n");
 101         else
 102             printf("NO\n");
 103     }
 104 }