HDU-1010 Tempter of the Bone

搜索 HDU-1010 Tempter of the Bone

题目链接：杭电1010

题目大意：小狗要逃生 只能四个方向走 且走过的地方不能再走 还只能在特定的时间逃生 不能多不能少

解题思路：正常的DFS 想的点要多一点 超时了三次 超时要return 到地方没到时间要return 最最重要的是走过的地方要标记为墙 防止出现出口堵住还瞎探索浪费时间的情况 注意这点的分支行不通时要将点还原

代码块：

#include<iostream>

using namespace std;

int n, m, t;
char str[10][10] = { '\0','\0' };
pair<int, int> beginn;
int xx[4] = { 0,1,-1,0 };
int yy[4] = { 1,0,0,-1 };
int bs = 0;

void dfs(int x, int y, int time);

int main() {
	while (cin >> n >> m >> t) {
		if ((n + m + t) == 0) return 0;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				cin >> str[i][j];
				//起点
				if (str[i][j] == 'S') {
					beginn.first = i;
					beginn.second = j;
				}
			}
		}
		dfs(beginn.first, beginn.second, 0);
		if (bs == 1) cout << "YES" << endl;
		else cout << "NO" << endl;
		bs = 0;
	}
	return 0;
}

void dfs(int x, int y, int time) {
	//超时死亡
	if (time > t) return;
	//到地方时没到时间死亡
	if (str[x][y] == 'D' && time != t) return;
	//到地方时刚好到时间 成功逃出
	if (str[x][y] == 'D' && time == t) {
		bs = 1;
		return;
	}
	str[beginn.first][beginn.second] = 'X';
	//走过的地方就不能再走了
	str[x][y] = 'X';
	for (int i = 0; i < 4; i++) {
		int dx = x + xx[i];
		int dy = y + yy[i];
		if (dx >= 1 && dx <= n && dy >= 1 && dy <= m && str[dx][dy] != 'X' && bs!=1) {//成功一次后不再调用
			dfs(dx, dy, time + 1);
		}
	}
	//如果从这级返回 那么相当于这个点没走 所以应该把这个点还原
	str[x][y] = '.';
	return;
}