[leetcode1631]最小体力消耗路径

昨天题太简单了。就一个前缀和 懒得写记录了
传送门：https://leetcode-cn.com/problems/path-with-minimum-effort/

从左上角到右下角 求最小相邻差的路径，即保证最小的路径最大差 这个题主要注意是求差

两种做法：

1. DFS/BFS搜路径 同时加二分 求能够到达的临界值 即大于等于ans时能够到达 小于ans时不能够到达的值 找这个值用二分去找就好了 差最大为1e6 详细思路见代码

#include
#include
#include <string.h>
#include
using namespace std;

const int dir[4][2] = {-1, 0, 1, 0, 0, -1, 0, 1};
class Solution
{
public:
int minimumEffortPath(vector<vector> &heights)
{
int m = heights.size(); //行
int n = heights[0].size(); //列
int l = 0, r = 1e6, ans = 0;
while (l <= r)
{
int mid = l + r >> 1;
queue<pair<int, int>> q;
q.push(make_pair(0, 0)); //起点入栈
int vis[m][n];
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
vis[i][j] = 0;
}
vis[0][0] = 1; //起点访问过
while (!q.empty())
{
pair<int, int> t = q.front();
q.pop();
for (int i = 0; i < 4; i++)
{
int nx = t.first + dir[i][0];
int ny = t.second + dir[i][1];
if (nx >= 0 && nx < m && ny >= 0 && ny < n && !vis[nx][ny] && abs(heights[t.first][t.second] - heights[nx][ny]) <= mid)
{
q.push(make_pair(nx, ny));
vis[nx][ny] = 1; //访问过该结点
}
}
}
if (vis[m - 1][n - 1])
{
ans = mid;
r = mid - 1;
}
else
{
l = mid + 1;
}
}
return ans;
}
};

2. 并查集 个人认为这个做法十分的巧妙 首先将所有边找出来 之后从小到大排序 之后不断地向并查集中加边 （注意：如果权值（两个节点之间的差）为1的边 插入1条和插入n条 对答案的贡献是一样的 所以很有可能 最后成功连通左上角和右下角的点的图有许多多余的边）直到加入到左上角和右下角连通 此时最后加入的边的值即为答案

const int maxn = 1e6 + 5;

// 并查集模板
class UnionFind
{
public:
vector parent;
vector size;
int n;
// 当前连通分量数目
int setCount;

public:
UnionFind(int _n) : n(_n), setCount(_n), parent(_n), size(_n, 1)
{
iota(parent.begin(), parent.end(), 0);
}

int findset(int x)
{
    return parent\[x\] == x ? x : parent\[x\] = findset(parent\[x\]);
}

bool unite(int x, int y)
{
    x = findset(x);
    y = findset(y);
    if (x == y)
    {
        return false;
    }
    if (size\[x\] < size\[y\])
    {
        swap(x, y);
    }
    parent\[y\] = x;
    size\[x\] += size\[y\];
    --setCount;
    return true;
}

bool connected(int x, int y)
{
    x = findset(x);
    y = findset(y);
    return x == y;
}

};

struct edg
{
int st, ed;
int n;
};

int cmp(edg a,edg b){
return a.n < b.n;
}

class Solution
{
public:
int minimumEffortPath(vector<vector> &heights)
{
int m = heights.size(); //行
int n = heights[0].size(); //列
vector mp; //mp存所有边
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
//加入所有边
int id = i * n + j; //计算每个点的哈希
if (i > 0)
{
edg t = {id - n, id, abs(heights[i][j] - heights[i - 1][j])};
mp.push_back(t);
}
if (j > 0)
{
edg t = {id - 1, id, abs(heights[i][j] - heights[i][j - 1])};
mp.push_back(t);
}
}
}
sort(mp.begin(), mp.end(), cmp);//从小到大排序 按照差值
UnionFind uf(m * n);
int ans = 0;
for(auto edge:mp){
uf.unite(edge.st, edge.ed);
if(uf.connected(0,m*n-1)){
ans = edge.n;
break;
}
}

    return ans;
}

};