# 1631. Path With Minimum Effort
###### tags: `LeetCode`
## **Link**
https://leetcode.com/problems/path-with-minimum-effort
## **Code**

class Solution {
public:
    int minimumEffortPath(vector<vector<int>>& heights) 
    {
        int n=heights.size(),m=heights[0].size(),ed=n*m-1,idx=-1;
        // 只有一格
        if(n==1 && m==1)
            return 0;
        vector<pair<int,pair<int,int>>> edge;
        p.resize(n*m);
        // disjoint set每個位置預設為自己
        for(int i=0;i<p.size();++i)
            p[i]=i;
        // 建邊的表
        for(int i=0;i<n;++i)
        {
            for(int j=0;j<m;++j)
            {
                // 每個點只要找右邊和下面的邊就可以了 也可以左邊和上面
                if(i+1<n)
                    edge.push_back({abs(heights[i][j]-heights[i+1][j]),{i*m+j,(i+1)*m+j}});
                if(j+1<m)
                    edge.push_back({abs(heights[i][j]-heights[i][j+1]),{i*m+j,i*m+j+1}});
            }
        }
        // 按邊長排序
        sort(edge.begin(),edge.end());
        // 當起點和終點在不同組的時候
        while(fp(0)!=fp(ed))
        {
            ++idx;
            // 如果現在這條邊的兩端點在不同組就合併
            if(fp(edge[idx].second.first)!=fp(edge[idx].second.second))
                p[fp(edge[idx].second.second)]=p[fp(edge[idx].second.first)];
        }
        // 最後一條加入的邊長即為題目的解
        return edge[idx].first;
    }
private:
    vector<int> p;
    int fp(int n)
    {
        if(p[n]!=n)
            return p[n]=fp(p[n]);
        return n;
    }
};

## 備註醬
我因為不想搞二維的disjoint set所以壓成一維了。
## date
**2023.09.16**

{%hackmd @nnks8908/background_leetcode %}