题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1010
题目大意：一只狗受到了骨头的诱惑，进了n*m的迷宫，迷宫的大门在第T秒开启。小狗要恰好在T秒到达。并且.只能走一次。
解题思路：BFS求最短时间，这里并不适合。因此dfs.dfs有3个状态dfs(i, j, t),表示到达(i, j)花费t秒。
这里要有剪枝：
剪枝1.目标状态（x1, y1),现在状态dd=(x2, y2) abs(x1-x2)+abs(y1-y2))表示现在状态到达目标状态的距离
tt=T-t表示还需要走的时间，if(tt-dd<0||(tt-dd)%2) return ; //这是不可能到达的情况
//PS:题目的输入很让人脑瓜子疼啊...WA屎我了..
书上的代码如下：
View Code
#include<stdio.h> #include<string.h> #include<math.h> #include<iostream> #include<cstdlib> using namespace std; int n, m, t, di, dj, flag; char map[10][10]; int dir[4][2]={{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; void dfs(int si, int sj, int cnt) { int i, xx, yy; if(si<=0||sj<=0||si>n||sj>m) return ; if(si==di&&sj==dj&&cnt==t) { flag=1; return ; } int temp=t-cnt-abs(si-di)-abs(sj-dj); if(temp<0 || temp%2) return ; for(i=0; i<4; i++) { xx=si+dir[i][0], yy=sj+dir[i][1]; if(map[xx][yy]!='X') { map[xx][yy]='X'; dfs(xx, yy, cnt+1); if(flag) return; map[xx][yy]='.'; } } return ; } int main() { int i, j, si, sj; while(scanf("%d%d%d", &n, &m, &t)!=EOF) { if(n==0&&m==0&&t==0) break; memset(map, 0, sizeof(map)); int wal=0; char temp; scanf("%c", &temp); for(i=1; i<=n; i++) { //scanf("%s%*c", map[i]); for(j=1; j<=m; j++) { scanf("%c", &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') wal++; } scanf("%c", &temp); } if(n*m-wal<=t) { 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; }