hdu1010――Tempter of the Bone（DFS+剪枝） (二)
[4][2] = {-1,0,1,0,0,-1,0,1};
void dfs(int si,int sj,int cnt)//深搜
{
if(si>=n || sj>=m || si<0 || sj < 0)//出界
return ;
if(cnt == t && si == di && sj == dj)//到达终点
flag = 1;
if(flag)
return ;
for(int i = 0; i<4; i++)
{
int nextx=si+to[i][0];
int nexty=sj+to[i][1];
if(nextx>=0&&nextx=0&&nexty>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++;//对“#计数”
}
if(n*m-wall<=t||abs(si-di)+abs(sj-dj)>
t)//t是代表要走的步数，步数加墙数必须小于总格子数的，因为所有格子中还包括了S和D，这是剪枝
{
printf("NO\n");
continue;
//abs(si-ei)+abs(sj-ej)为起点到终点的最短步数
}
if((abs(si-di)+abs(sj-dj))%2!=(t%2))
{
//狗走到门的时间必须和题目给定的时间是同奇同偶的，否则也不能在指定的那秒到达门
printf("NO\n");
continue;
}
flag = 0;
map[si][sj] = 'X';//出发点是不可能再走的了，变为墙
dfs(si,sj,0);
if(flag)
printf("YES\n");
else
printf("NO\n");
}
return 0;
}