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

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

两种做法：

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

#include <algorithm>
#include <queue>
#include <string.h>
#include <vector>
using namespace std;

const int dir[4][2] = {-1, 0, 1, 0, 0, -1, 0, 1};
class Solution
{
public:
    int minimumEffortPath(vector<vector<int>> &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<int> parent;
    vector<int> 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<int>> &heights)
    {
        int m = heights.size();    //行
        int n = heights[0].size(); //列
        vector<edg> 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;
    }
};