Rookie's way

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

Tempter of the Bone

/*//////////////////////////////////////////////////////////////////////////
 
 奇偶剪枝：把map看作
 0 1 0 1 0 1
 1 0 1 0 1 0
 0 1 0 1 0 1
 1 0 1 0 1 0
 0 1 0 1 0 1
 
 从 0->1 需要奇数步
 从 1->0 需要偶数步
 那么设所在位置 (si,sj) 与 目标位置 (di,dj) 
 如果abs(si-sj)+abs(di-dj)为偶数，则说明 abs(si-sj) 和 abs(di-dj)的奇偶性相同，需要走偶数步
 如果abs(si-sj)+abs(di-dj)为奇数，那么说明 abs(si-sj) 和 abs(di-dj)的奇偶性不同，需要走奇数步
 理解为 abs(si-sj)+abs(di-dj) 的奇偶性就确定了所需要的步数的奇偶性！！
 而 (t-cnt)表示剩下还需要走的步数，由于题目要求要在 t时 恰好到达，那么  (t-cnt) 与 abs(si-sj)+abs(di-dj) 的奇偶性必须相同
 因此 temp=t-cnt-abs(sj-dj)-abs(si-di) 必然为偶数！

///////////////////////////////////////////////////////////////////////////*/
#include <iostream>
using namespace std;
char map[8][8];
int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
int t,di,dj,si,sj;
int n,m;
bool escape;
void dfs(int si,int sj,int cnt)
{
   int i,temp;
   if (escape)return;
   if (si==di && sj==dj && cnt==t){escape=1;return;}
   if (si<=0 || sj<=0 || si>n || sj>m)return;   
   temp=t-cnt-abs(sj-dj)-abs(si-di);
   if (temp<0 || temp%2!=0)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],cnt+1);
           map[si+dir[i][0]][sj+dir[i][1]]='.';
       }
   }
}

int main()
{

    while (cin>>n>>m>>t)
    {
          if(n==0&&m==0&&t==0) break;
          escape=0;
          int wall=0;
          for (int i=1;i<=n;i++)
          {
              for (int j=1;j<=m;j++)
             {
               cin>>map[i][j];
               if (map[i][j]=='S'){si=i;sj=j;}
               if (map[i][j]=='D'){di=i;dj=j;}
               if (map[i][j]=='X'){wall++;}
             }
          }
          if (n*m-wall<=t)cout<<"NO\n";
          else
          {
              map[si][sj]='X';
              dfs(si,sj,0);
              if (escape)cout<<"YES\n";
              else
              cout<<"NO\n";
          }
    }
    return 0;
}