HDU1010 Temper of the Bone

2024-08-26 08:32

文章标签 hdu1010 temper bone

本文主要是介绍HDU1010 Temper of the Bone，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

刚刚上实验课，榨果汁。。。自觉学不到什么东西，就来到了机房，看看HDU上的题。一道搜索，其中包含了几个我从没想到过的剪枝方法，例如奇偶剪枝、路径剪枝还有在主函数中的一个剪枝，诸见代码与注释，虽然看起来没什么用的剪枝没准会遇到变态的测试数据导致最后的完蛋，所以只要能想到的剪枝就尽量写上去。
注：这题的代码来自标程。

/*Exe.Time    Exe.Memory  Code Len.   Language    Author62MS        1676K       2081 B      C++         int9
*/// PPT上的标程
#define LOCAL#include <iostream>
#include <cmath>
#include <fstream>using namespace std;// 迷宫地图
// X：墙壁，小狗不能进入
// S：小狗所处位置
// D：迷宫的门
// .：空格char map[9][9];
int n, m, t, di, dj;    // (di, dj):门的位置
bool escape;int dir[4][2] = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};/*1 1 1 1 1 1 1 1 11 0 0 0 0 0 0 0 11 0 0 0 0 0 0 0 11 0 0 0 0 0 0 0 11 0 0 0 0 0 0 0 11 0 0 0 0 0 0 0 11 0 0 0 0 0 0 0 11 0 0 0 0 0 0 0 11 1 1 1 1 1 1 1 1*/void dfs(int si, int sj, int cnt) // 表示在si，sj要求在cnt秒达到门的位置
// cnt 是当前的时间而非上述的注释
{int i, temp;if (si > n || sj > m || si <= 0 || sj <= 0) return;if (si == di && sj == dj && cnt == t) {escape = 1;return;}// 此处奇偶剪枝和路径剪枝temp = (t - cnt) - abs(si - di) - abs(sj - dj);if (temp < 0 || temp & 1) return;for (i = 0; i < 4; i++) {if (map[si + dir[i][0]][sj + dir[i][1]] != 'X') {map[si + dir[i][0]][sj + dir[i][1]] = 'X';dfs(si + dir[i][0], sj + dir[i][1], cnt + 1);if (escape) return;// backtrackmap[si + dir[i][0]][sj + dir[i][1]] = '.';}}return;
}// 到此这个DFS函数已经颇有效率，如果在此main函数中不进行剪枝也是可以的int main() {
#ifdef LOCALfreopen("input.txt", "r", stdin);
#endifstd::ios::sync_with_stdio(false);int i, j, si, sj;while (cin >> n >> m >> t && n && m && t) {// 此处数据是将要对对某些破烂数据的剪枝，可以删除掉int wall = 0;// Inputfor (i = 1; i <= n; i++) {for (j = 1; j <= m; j++) {cin >> 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') wall++;}}if (n * m - wall <= t) {cout << "NO" << endl;continue;}escape = 0;// 上述剪枝完毕，估计也没多少数据会用到上面这个剪枝，对效率提升不大map[si][sj] = 'X';dfs(si, sj, 0);if (escape) cout << "YES" << endl;else cout << "NO" << endl;}return 0;}