题目链接：Tempter of the Bone
第一次做剪枝的题目，剪枝，说实话研究的时间不短。好像没什么实质性的进展，遇到题目。绝对有会无从下手的感觉，剪枝越来越神奇了。
。。
。
HDU1010一道剪枝的经典题目，自己当初想用BFS过。提交了10几遍WA，后来查了是剪枝最终死心了
PS:第一次写剪枝题目，用了一个模拟地图来做奇偶性的判定条件进行剪枝，大牛们写的那种俺实在看不懂。渣渣儿。
。
。。
代码有点挫。
。
。
。562ms低空掠过
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
char ma[10][10];
bool vis[10][10];
bool mapp[10][10] = {{0,1,0,1,0,1,0,1,0,1},{1,0,1,0,1,0,1,0,1,0},{0,1,0,1,0,1,0,1,0,1},
{1,0,1,0,1,0,1,0,1,0},{0,1,0,1,0,1,0,1,0,1},{1,0,1,0,1,0,1,0,1,0},
{0,1,0,1,0,1,0,1,0,1},{1,0,1,0,1,0,1,0,1,0},{0,1,0,1,0,1,0,1,0,1},
{1,0,1,0,1,0,1,0,1,0}};
int n,m,T,dx,dy;
bool flag;
int mv[4][2]={{1,0},{0,-1},{0,1},{-1,0}};
void dfs(int sx,int sy,int dp)
{
if(dp==T&&sx==dx&&sy==dy)
{
flag=1; return ;
}
if(flag) return;
int t = T - dp;
if(mapp[sx][sy]==mapp[dx][dy]) //奇偶剪枝
{
if(t % 2) return ;
}
else
{
if(t % 2==0)
return ;
}
for(int i=0;i<4;i++)
{
int xx = sx + mv[i][0];
int yy = sy + mv[i][1];
if(ma[xx][yy]!='X' && vis[xx][yy]!=1 &&0<=xx && xx<n && 0<=yy && yy<m)
{
vis[xx][yy] = 1;
dfs(xx,yy,dp+1);
vis[xx][yy] = 0;
}
}
return;
}
int main()
{
int sx,sy;
while(~scanf("%d%d%d",&n,&m,&T))
{
if(n==0&&m==0&&T==0) break;
memset(vis,0,sizeof(vis));
for(int i=0;i<n;i++)
{
scanf("%s",ma[i]);
for(int j=0;j<m;j++)
{
if(ma[i][j]=='S')
{ sx=i; sy=j; }
else if(ma[i][j]=='D')
{ dx=i; dy=j; }
}
}
flag=0;
vis[sx][sy] = 1;
dfs(sx,sy,0);
(flag==1)? puts("YES"):puts("NO");
}
return 0;
}