1970. 你能穿过矩阵的最后一天
题目链接：1970. 你能穿过矩阵的最后一天
代码如下：
//参考链接：https://leetcode.cn/problems/last-day-where-you-can-still-cross/solutions/936629/dao-xu-bing-cha-ji-by-endlesscheng-canjclassUnionFind{public:UnionFind(intn):fa(n){// 一开始有n个集合 {0}，{1}...{n-1}//集合i的代表元是自己ranges::iota(fa,0);}//返回x所在集合的代表元//同时做路径压缩，也就是把x所在集合中所有元素的fa都改成代表元intfind(intx){//如果fa[x]==x,则表示x是代表元if(fa[x]!=x){fa[x]=find(fa[x]);//fa改成代表元}returnfa[x];}//判断x和y是否在同一个集合boolis_same(intx,inty){//如果x的代表元和y的代表元相同，那么x和y就在同一个集合//这就是代表元的作用：用来迅速判断两个元素是否在同一个集合returnfind(x)==find(y);}//把from所在集合合并到to所在集合中voidmerge(intfrom,intto){intx=find(from),y=find(to);fa[x]=y;// 合并集合，修改后就可以认为from 和 to在同一个集合了}private:vector<int>fa;// 代表元};classSolution{public:intlatestDayToCross(introw,intcol,vector<vector<int>>&cells){inttop=row*col;intbottom=row*col+1;UnionFinduf(row*col+2);vector<vector<int8_t>>land(row,vector<int8_t>(col));for(intday=cells.size()-1;;day--){auto&cell=cells[day];intr=cell[0]-1;// 改成从0开始的下标intc=cell[1]-1;intv=r*col+c;land[r][c]=true;//突变陆地if(r==0){uf.merge(v,top);// 与最上面相连}if(r==row-1){uf.merge(v,bottom);// 与最下面相连}for(auto&d:DIRS){intx=r+d[0],y=c+d[1];if(0<=x&&x<row&&0<=y&&y<col&&land[x][y]){uf.merge(v,x*col+y);//与四周的陆地相连}}//最上边和最下边相连if(uf.is_same(top,bottom)){returnday;}}}private://左右上下staticconstexprintDIRS[4][2]={{0,-1},{0,1},{-1,0},{1,0}};};
