本文主要是介绍HDU 1010--Tempter of the Bone，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：这是题目
题意：一只狗狗在一个迷宫里面要从门出去，但是门只在第T时间开一次，狗狗一定要在这个时间点出去，并且狗狗走过的路会消失，问是否狗狗能从门走出迷宫？
思路：这个题爆搜会T，要用奇偶剪枝，即T和狗狗到门的曼哈顿距离的奇偶一定要一样。
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <math.h>
using namespace std;const int MAX = 10;
int ti;int n, m, t;
char _map[MAX][MAX];
bool visit[MAX][MAX];
int d[MAX][MAX];
int x[4] = {0, 1, 0, -1};
int y[4] = {-1, 0, 1, 0};int dis(int x1, int y1, int x2, int y2) {return (abs(x2 - x1) + abs(y2 - y1));
}//计算曼哈顿距离bool dfs(int xx, int yy, int time) {if (_map[xx][yy] == 'D' && time == t) {return true;}//正好是t时刻到门则能到达else {for (int i = 0; i < 4; i++) {int xi = xx + x[i];int yi = yy + y[i];
// cout << "$$ " << xi << " " << yi << endl;if (xi >= 0 && xi < n && yi >= 0 && yi < m && !visit[xi][yi]) {
// cout << "ok " << xi << " " << yi << endl;time += 1;visit[xi][yi] = true;if (dfs(xi, yi, time)) {return true;}time -= 1;visit[xi][yi] = false;}}}return false;}int main() {while(scanf("%d%d%d", &n,&m,&t) != EOF) {if (n == 0 && m == 0 && t == 0)break;getchar();int sx, sy, ex, ey;ti = 100;memset(visit, false, sizeof(visit));for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {scanf("%c", &_map[i][j]);if (_map[i][j] == 'S') {sx = i;sy = j;visit[sx][sy] = true;}else if (_map[i][j] == 'D') {ex = i;ey = j;}else if (_map[i][j] == 'X')visit[i][j] = true;}getchar();}if (dis(sx, sy, ex, ey) % 2 == t % 2) {//剪枝if (dfs(sx, sy, 0))printf("YES\n");elseprintf("NO\n");}else {printf("NO\n");}}return 0;
}这篇关于HDU 1010--Tempter of the Bone的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
