题目大意:输入三个整数N,M,T。在接下来的N行、M列会有一系列的字符。其中S表示起点，D表示终点。 .表示路 。 X表示墙。。。问狗能有在T秒时到达D。如果能输出YES，
否则输出NO
解题思路：DFS+剪枝
代码如下:
/*
* 1010_3.cpp
*
* Created on: 2013年8月16日
* Author: Administrator
*/ #include <iostream> using namespace std; bool flag;
int N, M, T;
int si, sj;
int ei, ej; const int maxn = 8;
int dir[4][2] = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
char map[maxn][maxn]; bool checkEdge(int x, int y) {
if (!(x < 1 || x > N || y < 1 || y > M)) {
return true;
} return false;
} void dfs(int curX, int curY, int curT) {
if (flag) {//如果找到出口，直接返回
return;
} if (curT > T) {//如果当前花费的时间大于T，就返回
return;
} //花费的时间加上剩余需要的时间若大于T，返回
if (curT + abs(curX - ei) + abs(curY - ej) > T) {
return;
} //若到达出口最短距离和剩余时间的奇偶性不同，返回
if ((abs(curX - ei) + abs(curY - ej)) % 2 != abs(T - curT) % 2) {
return;
} if (curX == ei && curY == ej && curT == T) {
printf("YES\n");
flag = true;
return;
} int i;
for (i = 0; i < 4; ++i) {
int nextX = curX + dir[i][0];
int nextY = curY + dir[i][1]; if (checkEdge(nextX, nextY)) {
if (map[nextX][nextY] != 'X') {
map[nextX][nextY] = 'X';//使其不可达到
dfs(nextX, nextY, curT + 1);
map[nextX][nextY] = '.';//回溯时，恢复原来的状态
}
}
}
}
int main() {
while (scanf("%d%d%d", &N, &M, &T) != EOF, N || M || T) {
getchar();
int k = 0;
int i, j;
flag = false;
memset(map, 0, sizeof(map));
for (i = 1; i <= N; ++i) {
for (j = 1; j <= M; ++j) {
scanf("%c", &map[i][j]); if (map[i][j] == 'S') {
si = i;
sj = j;
map[i][j] = 'X'; //将开始位置置为不可达状态
} else if (map[i][j] == 'D') {
ei = i;
ej = j;
} if (map[i][j] != 'X') {
++k;
}
}
getchar();
} if (k < T) {//若可走的点数小于T，则输出NO
printf("NO\n");
continue;
} dfs(si, sj, 0); if (!flag) {
printf("NO\n");
}
}
}