查看完整版本: poj 2922 Honeymoon Hike解题报告源代码

poj 2922 Honeymoon Hike解题报告源代码

题目来源：POJ 2922 Honeymoon Hike
                        [url]http://acm.pku.edu.cn/JudgeOnline/problem?id=2922[/url]
                                TOJ 2344 Honeymoon Hike
                        [url]http://acm.tju.edu.cn/toj/showp.php?pid=2344[/url]

解法类型：二分查找+深度优先搜索

题目大意：
给出一个图中各个点的高度，从所给图的左上角走到右下角，求所有路径中最高点和最低点高度差最小的路径。

解题思路：
二分查找高度差，根据每次的高度差枚举上下界，进行深度优先搜索判断该上下界是否可以走通。

提交情况：
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[j];//输入图
                cout<<"Scenario #"<<caseCount<<":"<<endl;
                cout<<search(0,200)<<endl<<endl;//输出结果
        }
        return 0;
}