程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> poj 2922 Honeymoon Hike

poj 2922 Honeymoon Hike

編輯:C++入門知識

題意:給定一個n*n地圖和高度,一個人從左上角地圖開始,需要走到右下角的地圖,問他走的路程中所到達的最大高度和最小高度的差最小是多少。

思路:二分答案,對於每一個高度差,可以用dfs或bfs檢驗是否能夠到達目的地,一開始想法是每次傳以前的最大和最小高度,然後在更新,這樣重疊檢驗會超時,然後參考博客,需要枚舉區間來優化。於是可以改枚舉高度區間的辦法來縮減時間。以起始點高度h,[h-mid,h]~[h,h+mid]。

 

#include <iostream>   
#include <algorithm>   
#include <cmath>   
#include <cstdio>   
#include <cstdlib>   
#include <cstring>   
#include <string>   
#include <vector>   
#include <set>   
#include <queue>   
#include <stack>   
#include <climits>//形如INT_MAX一類的   
#define MAX 105   
#define INF 0x7FFFFFFF   
# define eps 1e-5   
using namespace std;  
  
int map[MAX][MAX];  
int vis[MAX][MAX];  
int dirx[4]= {1,0,0,-1};  
int diry[4]= {0,1,-1,0};  
int n,judge,small,big;  
  
bool ok(int x,int y)  
{  
    if(x < 0 || x >= n || y < 0 || y >= n)  
        return false;  
    return true;  
}  
  
int dfs(int x,int y)  
{  
    if(map[x][y] < small || map[x][y] > big)  
        return 0;  
    if(x == n-1 && y == n-1)  
    {  
        return 1;  
    }  
    vis[x][y] = 1;  
    for(int i=0; i<4; i++)  
    {  
        int xx = x + dirx[i];  
        int yy = y + diry[i];  
        if(ok(xx,yy) && !vis[xx][yy])  
        {  
            if(dfs(xx,yy))  
                return 1;  
        }  
    }  
    return 0;  
}  
  
int main()  
{  
    int t,i,j;  
    int Casee=1;  
    cin >> t;  
    while(t--)  
    {  
        cin >> n;  
        int high=0,low=205,mid;  
        for(i=0; i<n; i++)  
            for(j=0; j<n; j++)  
            {  
                scanf("%d",&map[i][j]);  
                if(high < map[i][j])  
                    high = map[i][j];  
                if(low > map[i][j])  
                    low = map[i][j];  
            }  
        printf("Scenario #%d:\n",Casee++);  
  
        int ans = 0;  
        high -= low;  
        low = 0;  
        mid = (high + low)/2;  
        while(low <= high)  
        {  
            small = max(map[0][0]-mid,0);  
            for(; small<=map[0][0]; small++)  
            {  
                big = small + mid;  
                memset(vis,0,sizeof(vis));  
                if(dfs(0,0))  
                {  
                    ans = mid;  
                    break;  
                }  
            }  
            if(small <= map[0][0])  
                high = mid - 1;  
            else  
                low = mid + 1;  
            mid = (high+ low)/2;  
        }  
        printf("%d\n",ans);  
        cout << endl;  
    }  
    return 0;  
}  

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved