[leetcode]1631. 最小体力消耗路径(bool类型dfs+二分答案/记忆化剪枝/并查集Kruskal思想)

题目链接

题意

给定 $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;}};