題意:給定一個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; }