題目鏈接

題意

給定$n\times m$地圖 要從(1,1) 走到 (n,m)
定義高度絕對差為四聯通意義下相鄰的兩個點高度的絕對值之差
定義路徑的體力值為整條路徑上 所有高度絕對差的max
求所有路徑中 最小的路徑體力值是多少

方法1

這是我一開始自己寫的記憶化剪枝
比較暴力 時間復雜度很高 但是能勉強通過

思路

dfs枚舉每條路徑 對ans取min
但是會超時 那么加上記憶化剪枝

Code

void cmax(int &a,int b){a=max(a,b);};
void cmin(int &a,int b){a=min(a,b);};
const int N=110;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
int g[N][N],dp[N][N];//dp表示從(1,1)走到(i,j)的最小體力值
bool vis[N][N];
int n,m;class Solution {
public:int ans=0x3f3f3f3f;//ans必須定義在類內部 因為定義在全局會被上一個測試用例修改int minimumEffortPath(vector<vector<int>>& heights) {n=heights.size(),m=heights[0].size();memset(dp,0x3f,sizeof dp);for(int i=0;i<n;i++){for(int j=0;j<m;j++){g[i+1][j+1]=heights[i][j];}}vis[1][1]=1;dfs(1,1,0);return ans;}void dfs(int x,int y,int res){if(res>ans) return;if(x==n&&y==m){cmin(ans,res);return;}for(int i=0;i<4;i++){int tx=x+dx[i],ty=y+dy[i];if(tx<1||tx>n||ty<1||ty>m||vis[tx][ty]) continue;int now=max(abs(g[tx][ty]-g[x][y]),res);if(dp[tx][ty]<=now) continue;//如果從(tx,ty)這個點已經搜過了 //并且之前存的比當前搜的更優 那么就放棄當前這個點dp[tx][ty]=now;//當前更優 vis[tx][ty]=1;dfs(tx,ty,now);vis[tx][ty]=0;}}   
};

方法2

思路

最大值最小化 ->二分答案
對路徑體力值二分 每次check就是dfs一下能不能在這個高度絕對差不超過mid 的情況下走到終點

Code

#define pii pair<int,int>
#define ar2 array<int,2>
#define ar3 array<int,3>
#define ar4 array<int,4>
#define endl '\n'
void cmax(int &a,int b){a=max(a,b);};
void cmin(int &a,int b){a=min(a,b);};
const int N=110,MOD=1e9+7,INF=0x3f3f3f3f;const long long LINF=LLONG_MAX;const double eps=1e-6;
int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
int n,m,g[N][N];
bool vis[N][N];bool dfs(int x,int y,int k){if(x==n&&y==m) return 1;for(int i=0;i<4;i++){int tx=x+dx[i],ty=y+dy[i];if(tx<1||tx>n||ty<1||ty>m||vis[tx][ty]) continue;int d=abs(g[x][y]-g[tx][ty]);if(d<=k){vis[tx][ty]=1;bool flag=dfs(tx,ty,k);if(flag) return 1;}}return 0;
}class Solution {
public:int minimumEffortPath(vector<vector<int>>& heights) {n=heights.size(),m=heights[0].size();for(int i=0;i<n;i++){for(int j=0;j<m;j++){g[i+1][j+1]=heights[i][j];}}int l=-1,r=1e6+1;while(l+1!=r){int mid =l+r>>1;memset(vis,0,sizeof vis);vis[1][1]=1;if(dfs(1,1,mid)) r=mid;else l=mid;}return r;}
};

實現細節

• 每次二分要初始化vis數組 并且注意要把起點設為true
• 重點看bool類型dfs的實現
• • bool dfs(int x,int y,int k)表示從 (x,y)出發 以k為限制能否到達終點
• • 與常見的dfs枚舉路徑方案不同 這里不需要枚舉全部方案 而是只需要找到一個方案能夠到達終點就可以
• • 不需要回溯 把vis[tx][ty]=0 因為一旦這個點可以走(從(x,y)到(tx,ty)不超過k到限制) 那么就會被標記為true 然后dfs往下走
• • 如果從(tx,ty)不能到終點 那么dfs會返回false 所以這個點就沒有價值了 不需要回溯 如果標記回去 從別的點再次走到這個點是沒有意義的 這個點已經搜過了 不可能走到終點
• • 如果dfs從(tx,ty)往下搜 能到終點 就立刻返回true 如果四聯通都走了一遍也沒return true 那么說明不行 就return false

方法3

思路

Kruskal的思想
把每條邊存下來 按邊權排序
用并查集維護 一旦起點和終點在一個聯通塊內 就返回此時的邊權（因為排序過了 一定是最大的邊權）


這里不需要關心每一步具體是怎么走的
只需要維護每個點的聯通關系即可 只要起點和終點聯通 就代表一條完整的路徑出現了 這個思路太妙了 實現起來很快

Code

void cmax(int &a,int b){a=max(a,b);};
void cmin(int &a,int b){a=min(a,b);};
const int N=110;
int p[N*N];
int n,m;int find(int x){if(p[x]!=x) p[x]=find(p[x]);return p[x];
}struct node{int w,u,v;
};class Solution {
public:int minimumEffortPath(vector<vector<int>>& g) {n=g.size(),m=g[0].size();for(int i=0;i<=n*m;i++) p[i]=i;//建圖vector<node>edges;for(int i=0;i<n;i++){for(int j=0;j<m;j++){int id=i*m+j;if(i>0){edges.push_back((node){abs(g[i-1][j]-g[i][j]),id-m,id});}if(j>0){edges.push_back((node){abs(g[i][j-1]-g[i][j]),id-1,id});}}}sort(edges.begin(),edges.end(),[](const auto& e1,const auto& e2){return e1.w<e2.w;});int ans=0;for(auto[w,u,v]:edges){int uu=find(u),vv=find(v);p[vv]=uu;//不要寫成uu=p[vv];if(find(0)==find(n*m-1)){ans=w;break;}}return ans;}};

實現細節

關鍵是在建圖
兩重循環遍歷 每個點都跟他上面以及左邊的點建邊（如果有的話）
這樣就很方便的 不重不漏地把所有的邊都建起來了
存邊的時候節點編號做一個簡單的狀態壓縮即可