[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;}};

实现细节

关键是在建图
两重循环遍历 每个点都跟他上面以及左边的点建边（如果有的话）
这样就很方便的 不重不漏地把所有的边都建起来了
存边的时候节点编号做一个简单的状态压缩即可