原文地址：http://www.cnblogs.com/goodness/archive/2010/03/05/1678891.html
题目来源：POJ 2922 Honeymoon Hike
http://acm.pku.edu.cn/JudgeOnline/problem?id=2922
TOJ 2344 Honeymoon Hike
http://acm.tju.edu.cn/toj/showp.php?pid=2344
解法类型：二分查找+深度优先搜索
题目大意：
给出一个图中各个点的高度，从所给图的左上角走到右下角，求所有路径中最高点和最低点高度差最小的路径。
解题思路：
二分查找高度差，根据每次的高度差枚举上下界，进行深度优先搜索判断该上下界是否可以走通。
提交情况：
1、 Time Limit Exceeded一次：没有枚举上下界，而是根据高度差进行深搜，不断更新上下界，深搜的耗时太长。枚举上下界虽然需要耗费一定时间，但由于此题上下界范围较小，枚举后可大大减少深搜的时间，总体时间仍可减少。
2、 Wrong Answer两次，清空标记数组的时候没有在每次上下界枚举时更新，导致标记数组混乱。
注意：
此题对时间的分析要求较高，不ac时，需找寻缩减时间可能的突破口，并通过此突破口进行编码、尝试。
源程序：
#include <iostream> using namespace std; long h[110][110], t[110][110], n; int dfs(long row, long col, long dn, long up) { //通过上下界进行深搜 if(h[row][col] > up || h[row][col] < dn) return 0; //当前搜索位置不满足上下界，返回0 t[row][col] = 1; //满足则标记该位置已经被搜索过 if(row == n && col == n) return 1; //已经搜索到目的位置，返回1 if(row >= 2 && t[row-1][col] == 0 && dfs(row - 1, col, dn, up)) return 1; if(col >= 2 && t[row][col-1] == 0 && dfs(row, col - 1, dn, up)) return 1; if(row + 1 <= n && t[row+1][col] == 0 && dfs(row + 1, col, dn, up)) return 1; if(col + 1 <= n && t[row][col+1] == 0 && dfs(row, col + 1, dn, up)) return 1; return 0; //向四个方向进行搜索，如果均不可达则返回0 } long search(long min, long max) { long mid, tmp, dn; while(min < max) //二分查找 { mid = (max + min) / 2; tmp = h[1][1] - mid; for(dn = tmp > 0 ? tmp : 0; dn <= h[1][1]; dn++ ) //枚举上下界 { memset(t, 0, sizeof(t)); //清空标记数组 if(dfs(1, 1, dn, dn + mid)) break; //判断该上下界是否可行 } if(dn <= h[1][1]) max = mid; else min = mid + 1; } return max; } int main() { long i, j, k, caseNum, caseCount; cin >> caseNum; for(caseCount = 1; caseCount <= caseNum; caseCount++) { cin >> n; for(i = 1; i <= n; i++) for(j = 1; j <= n; j++) cin >> h[i][j]; //输入图 cout << "Scenario #" << caseCount << ":" << endl; cout << search(0, 200) << endl << endl; //输出结果 } return 0; }