題目

農(nóng)夫約翰和貝西牛已經(jīng)開始了其中一個(gè)“積極”的假期。他們整天都在山里散步，然后在一天結(jié)束時(shí)，他們厭倦了回到度假小屋。

由于攀爬需要大量能量并且已經(jīng)疲憊，他們希望使用其最高和最低高度之間的差異最小的路徑返回到機(jī)艙，無論路徑有多長。幫助FJ找到這條易于移動(dòng)的路徑。

山的地圖由N×N（2 <= N <= 100）整數(shù)高程矩陣給出（0 <=任意高程<= 110）FJ和Bessie當(dāng)前位于左上角位置（第1行，列） 1）并且艙室位于右下方（第N行，第N列）。它們可以向右，向左，向頂部或向網(wǎng)格底部移動(dòng)。他們不能在對角線上旅行。
輸入
*第1行：單個(gè)整數(shù)，N

*行2…N + 1：每行包含N個(gè)整數(shù)，每個(gè)整數(shù)指定一個(gè)正方形的高度。第2行包含網(wǎng)格的第一行（頂部）; 第3行包含第二行，依此類推。該行上的第一個(gè)數(shù)字對應(yīng)于網(wǎng)格的第一個(gè)（左）列，依此類推。
產(chǎn)量
*第1行：一個(gè)整數(shù)，它是最佳路徑上的最小高度差。
樣本輸入
5
1 1 3 6 8
1 2 2 5 5
4 4 0 3 3
8 0 2 3 4
4 3 0 2 1
樣本輸出
2

分析與解答

這題根滑雪那到一樣，用普通的搜索根本沒法寫，因?yàn)閺V搜每個(gè)節(jié)點(diǎn)只訪問一次，而這個(gè)并不是只找一條路。深搜的話找路徑需要記錄當(dāng)前DFS路徑上所遇到所有點(diǎn)的高度，有些路徑中的某個(gè)點(diǎn)高度過高，一看就知道不需要走，但是深搜還是要走，所以時(shí)間上浪費(fèi)

這題利用二分，我們二分的是個(gè)高度差，就是說當(dāng)前高度差處于[low,up]這個(gè)區(qū)間的范圍之中，對于這個(gè)區(qū)間[low,up]我們用BFS找,看看能不能找到一條從左上角到右下角的路,

我們bfs參數(shù)是數(shù)的高度，他們的高度差我們二分出來了，現(xiàn)在就不斷枚舉所有可能的起止高度進(jìn)行遍歷，比如高度差位mid，那么區(qū)間就是（low，low+mid）low從一遞增到一百一.。只要有一個(gè)路徑的數(shù)都在區(qū)間里面我們就return
bfs從（1，1）開始搜，先判斷起點(diǎn)是不是在區(qū)間范圍內(nèi)，不是的話返回，是的話入隊(duì)，然后只要隊(duì)不空，取隊(duì)首，然后上下左右移動(dòng)，一般的bfs，只要是第一次出現(xiàn)，在這個(gè)區(qū)域內(nèi)，就入隊(duì)了，這個(gè)區(qū)間的bfs 是有選擇的入隊(duì)，只有屬于我們規(guī)定的的區(qū)間的我們才讓他入隊(duì)，就這么一直如下去，如果碰到這個(gè)坐標(biāo)是（n，n）就說明已經(jīng)找到了屬于這個(gè)區(qū)間的路徑，返回true
注意兩個(gè)if的順序，四個(gè)方向能走的不一定在這個(gè)區(qū)間里

參考代碼：

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; const int maxn=105; int map[maxn][maxn]; int vis[maxn][maxn]; int n; int to[4][2]={{-1,0},{1,0},{0,-1},{0,1}}; struct node{int x,y; };int bfs(int l,int r) {if(map[1][1]<l||map[1][1]>r) return 0;queue<node> q;node k;k.x=1;k.y=1;q.push(k);vis[1][1]=1;while(!q.empty()){node a,b;b=q.front();q.pop();int x=b.x;int y=b.y;for(int j=0;j<4;++j){int ax=x+to[j][0];int ay=y+to[j][1];if(ax>=1&&ax<=n&&ay>=1&&ay<=n&&!vis[ax][ay]){vis[ax][ay]=1;if(map[ax][ay]>=l&&map[ax][ay]<=r){if(ax==n&&ay==n) return true; a.x=ax;a.y=ay;q.push(a);}}}}return false;}int check(int d){for(int i=0;i+d<=110;i++){memset(vis,0,sizeof(vis));if(bfs(i,i+d)) return 1; }return false;} int main() {scanf("%d",&n);for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)scanf("%d",&map[i][j]);int l=0,r=110;while(r>l){int mid = (r+l)/2;if(check(mid)) r=mid;else l=mid+1;}printf("%d\n",r);return 0; } }

欣賞一下dfs

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn=100+5; int n; int map[maxn][maxn]; int vis[maxn][maxn];//判斷當(dāng)前節(jié)點(diǎn)時(shí)候被走過 int max_v,min_v; int dr[]={-1,1,0,0};//上下左右 int dc[]={0,0,-1,1}; bool dfs(int r,int c,int low,int up) {vis[r][c]=1; //錯(cuò)誤,這里之前vis放到了if下面if(map[r][c]>up || map[r][c]<low) return false;if(r==n&&c==n) return true; //到達(dá)終點(diǎn)for(int dir=0;dir<4;dir++){int nr=r+dr[dir],nc=c+dc[dir];if(nr>=1&&nr<=n&&nc>=1&&nc<=n&&!vis[nr][nc])if(dfs(nr,nc,low,up)) return true; //錯(cuò)誤,這里忘了返回true了}return false; } bool check(int d) {for(int low=0;low+d<=200;low++){memset(vis,0,sizeof(vis)); //錯(cuò)誤,這里memset放到了for上面if(dfs(1,1,low,low+d)) return true;}return false; } int main() {int T; scanf("%d",&T);for(int kase=1;kase<=T;kase++){scanf("%d",&n);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)scanf("%d",&map[i][j]);int L=0,R=200;while(R>L){int mid=(R+L)>>1;if(check(mid)) R=mid;else L=mid+1;}//printf("Scenario #%d:\n%d\n\n",kase,R);printf("%d\n",R);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的（二分+区间搜索 ）Mountain Walking（poj2110/poj2922）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。