hdu1010_tempter_of_the_Bone(dfs减枝)

本文主要是介绍hdu1010_tempter_of_the_Bone(dfs减枝)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目大意：在一个矩阵之中从S到D在规定的时间到达，不能走回头路。题目的连接hdu1010
解题思路：因为到达的时间是固定的，因此使用广度优先遍历是不行的，广度优先遍历只能找到由S到达D的最小时间而不能找到规定的时间。因此要使用深度优先遍历，而深度优先遍历要注意减枝来提高最终的效率。
设当前的坐标为i，j。那么由当前位置到终点（ex，ey）的最短距离为以两个点为对角线的矩形的长和宽之和减2，或者使用abs（ex-i）+abs（ey-j）得到结果。那么最小的距离一定要小于等于剩余的步数，如果大于打话就不能再走下去，需要减枝。
另一个减枝条件需要一些讲解，每一个举证都可以用0和1进行如下的处理，以4*4的矩阵为例
0 1 0 1
1 0 1 0
0 1 0 1
1 0 1 0
0 和 1 表示对应为的奇偶性，很容易看出，如果两个点的奇偶性相同，则到达的步数为偶数，如果奇偶性不同，则到达的步数为奇数。因此在对矩阵进行处理之前就可以确定是否能求不结果。
另外一个减枝是在开始的时候，统计所有的非’X’的个数sum，如果sum-1小于给的步数，那么一定不能到达终点。

#include<iostream>
#include<algorithm>
using namespace std;char maze[10][10];
int N,M,T;
int ex,ey;void check()
{for(int i=0;i<N;i++){for(int j=0;j<M;j++)        {printf("%c ",maze[i][j]);  }putchar(10);}getchar();getchar();
}bool dfs(int i,int j)
{//check();int minb = abs(ex-i)+abs(ey-j);if(minb>T)return false;     if(i-1>=0){   if(maze[i-1][j]=='D'){if(T==1)return true;}else if(maze[i-1][j]!='X'){T--;maze[i][j]='X';if(dfs(i-1,j))return true; T++;maze[i][j]='.';}}//下if(i+1<N){   if(maze[i+1][j]=='D'){if(T==1)return true;}else if(maze[i+1][j]!='X'){T--;maze[i][j]='X';if(dfs(i+1,j))return true; T++;maze[i][j]='.';             }}//左if(j-1>=0){   if(maze[i][j-1]=='D'){if(T==1)return true;}else if(maze[i][j-1]!='X'){T--;maze[i][j]='X';if(dfs(i,j-1))return true; T++;maze[i][j]='.';}}//右 if(j+1<M){   if(maze[i][j+1]=='D'){if(T==1)return true;}else if(maze[i][j+1]!='X'){T--;maze[i][j]='X';if(dfs(i,j+1))return true; T++;maze[i][j]='.';}}return false;
}int main()
{int sx,sy;while(1){scanf("%d%d%d",&N,&M,&T);if(N==0&&M==0&&T==0) break;for(int i=0;i<N;i++){getchar();for(int j=0;j<M;j++){scanf("%c",&maze[i][j]);if(maze[i][j]=='S'){sx=i;sy=j;}else if(maze[i][j]=='D'){ex=i;ey=j;      }}}getchar();if(((sx+sy)%2==(ex+ey)%2&&T%2!=0)||((sx+sy)%2!=(ex+ey)%2&&T%2==0)){printf("NO\n");                                                                  }else{if(!dfs(sx,sy))printf("NO\n");else printf("YES\n");}}return 0;    
}
//注意接收数据
//注意就减枝