本文主要是介绍HDU 1010 Tempter of the Bone (搜索)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
OJ题目 ： click here ~~
大概题意 ： 迷宫搜索。从起点到终点 ，不能回头 ， 问能不能在恰好在T 时刻，准时到达终点。
本题充分体现了剪枝的重要性：
奇偶性剪枝：
可以把maze看成这样：
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 的格子
即：
0 ->1或1->0 必然是奇数步
0->0 走1->1 必然是偶数步
结论：
所以当遇到从 0 走向 0 但是要求时间是奇数的，或者， 从 1 走向 0 但是要求时间是偶数的 都可以直接判断不可达！
AC_CODE
int N , M , T;
int maze[8][8];
int dir[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};
int sx , sy , ex , ey;
int escape;bool cango(int x, int y)
{return 1 <= x && x <= N && 1 <= y && y <= M && maze[x][y] != 'X';
}void dfs(int x , int y , int t)
{if(x == ex && y == ey && t == T) escape = 1;if(escape) return ;int temp = (T - t) - abs(ex - x) - abs(ey - y);if(temp < 0 || temp&1) return ;//剪枝：时间不够，或者奇偶性不一致，则返回for(int i = 0;i < 4;i++){int nx = x + dir[i][0];int ny = y + dir[i][1];if(cango(nx,ny)){maze[nx][ny] = 'X';dfs(nx , ny , t + 1);maze[nx][ny] = '.';}}return ;
}int main()
{while(scanf("%d%d%d",&N ,&M ,&T)){if(N == 0 && M == 0 && T == 0) break;int i , j , walknum = 0;char *s = new char;for(i = 1;i <= N;i++){scanf("%s",s);for(j = 1;j <= M;j++){maze[i][j] = s[j - 1];if(maze[i][j] == 'S'){sx = i;sy = j;}else if(maze[i][j] == 'D'){ex = i;ey = j;walknum++;}else if(maze[i][j] == '.' )walknum++;}}if(walknum < T)//剪枝：能走的block数小于T的话，则肯定不能达到。{printf("NO\n");continue;}maze[sx][sy] = 'X';escape = 0;dfs(sx , sy , 0);if(escape) printf("YES\n");else printf("NO\n");}return 0;
}这篇关于HDU 1010 Tempter of the Bone (搜索)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
