http://acm.hdu.edu.cn/showproblem.php?pid=1010
#include<iostream>
using namespace std;
char gra[8][8];
bool mark[8][8];
int m,n,t,ok;
int si,sj,ei,ej;
int dir[4][2]={-1,0,1,0,0,-1,0,1};

int fun(int a,int b)
{
    if(a>b)
        return a-b;
    else
        return b-a;
}

void dfs(int i,int j,int step)
{
    int k,p,q;
    if(ok == 1)
        return ;
    if(step == t)
    {
        if(i == ei && j == ej)
            ok = 1;
        return ;
    }
    k = fun(i,ei) + fun(j,ej) ;
    if(step + k > t) //最快的时间都不能走到，肯定完蛋了
        return ;
    if(k % 2 != (t-step) % 2)//if((t - step - k) & 1) //奇偶剪枝
        return ;
    /**//*
       1 1 1 1 1 1
       1 0 1 1 1 1
       1 1 1 1 1 1
       1 1 1 1 1 1
       1 1 1 1 0 1
       两个0之间的坐标之差为6，是偶数，只能走偶数步才能到达
    */
    for(k=0;k<4;k++)
    {
       p = i + dir[k][0];
       q = j + dir[k][1];
       if(p>=0 && p<m && q>=0 && q<n && gra[p][q]!='X' && mark[p][q] == 0)
       {
            mark[p][q] = 1;
            dfs(p,q,step+1);
            mark[p][q] = 0;
       }
    }
}
int main()
{
    while(cin>>m>>n>>t && m+n+t)
    {
        int i,j,walls=0;
        for(i=0;i<m;i++)
            for(j=0;j<n;j++)
            {
                cin>>gra[i][j];
                if(gra[i][j] == 'S')
                {
                    si = i;
                    sj = j;
                }
                else if(gra[i][j] == 'D')
                {
                    ei = i;
                    ej = j;
                }
                else if(gra[i][j] == 'X')
                    walls++;
                mark[i][j] = 0;
            }
        if(n*m-walls<=t)
        {
           cout<<"NO"<<endl;
           continue;
        }
        ok = 0;
        mark[si][sj] = 1;
        dfs(si,sj,0);
        if(ok == 1)
            cout<<"YES"<<endl;
        else
            cout<<"NO"<<endl;
    }
    return 0;
}