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

poj 2110 Mountain Walking 枚舉+bfs

編輯:關於C++

題意:

給一個n*n的矩陣,要從左上角走到右下角,使經過數字的最大數與最小數的差最小。

分析:

一開始想到了二分這個差,然後判斷是否存在路徑,每次只知道差的話深搜每次搜索要記錄沿途的最大值和最小值會tle,廣搜的話如果節點只記錄x,y坐標,搜索中存在要重新訪問以前訪問過節點的情況,比如一開始(1,1)->(1,2)->(2,2),如果(2,1)這個點的值更合適,最優訪問路徑(1,1)->(2,1)->(2,2),也就是(2,2)要被重新訪問,不滿足廣搜每個節點只訪問一次的原則,只有增加節點維度每個節點記錄x,y坐標和到達它經過的最小最大值,顯然不好。後來了解到可以加大枚舉,不僅枚舉差,還枚舉路徑上的最大值,這樣每次路徑上的最大最小值就確定了,可以廣搜。

 

//poj 2110
//sep9
#include 
#include 
using namespace std;
const int maxN=128;
struct Node
{
	int x,y;		
};

int g[maxN][maxN];
int vis[maxN][maxN];
int dirx[4]={0,0,-1,1};
int diry[4]={-1,1,0,0};
int n,diff,min_hight,max_hight;
queue q;


bool pass(int low,int high)
{
	memset(vis,0,sizeof(vis));
	Node a;
	a.x=1,a.y=1;
	if(g[1][1]>high||g[1][1]=1&&nx<=n&&ny>=1&&ny<=n&&vis[nx][ny]==0&&g[nx][ny]<=high&&g[nx][ny]>=low){
				Node a;
				a.x=nx,a.y=ny;
				q.push(a);
				vis[nx][ny]=1;
				if(nx==n&&ny==n) return true;
			}	
		}
	}
	return false;		
}

bool work(int mid)
{
	for(int high=min_hight;high<=max_hight;++high){
		int low=high-mid;	
		if(pass(low,high))
			return true;
	}
	return false;

}

int main()
{
	scanf("%d",&n);
	min_hight=INT_MAX;
	max_hight=INT_MIN; 
	for(int i=1;i<=n;++i)
		for(int j=1;j<=n;++j){
			scanf("%d",&g[i][j]);
			min_hight=min(min_hight,g[i][j]);
			max_hight=max(max_hight,g[i][j]); 
		}
	int ans,l=0,r=max_hight+1,mid;
	while(l

 

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