题目链接： J. Maze Designer
题解：把边界看成边然后，要求任意两点是只有一条最短路，很明显是颗树。然后求一颗最大生成树，加个lca,求两点距离就好了
#include<bits/stdc++.h> #include <iostream> #include <string.h> #include <algorithm> #include <stdio.h> #include <math.h> #define ll long long #define pb push_back using namespace std; const int N=3e5+7; struct edge { int u,v,l; bool operator<(const edge b)const { return l>b.l; } }; multiset<edge>st; int f[N],dep[N],fa[N][20],n,m; void init() { for(int i=0;i<N;i++)f[i]=i; } vector<int>g[N]; int find(int x) { return x==f[x]?x:f[x]=find(f[x]); } void dfs(int v,int f,int d) { dep[v]=d; fa[v][0]=f; for(int to:g[v]) { if(to!=f) { dfs(to,v,d+1); } } } int lca(int x,int y) { if(dep[x]<dep[y])swap(x,y); int k=dep[x]-dep[y]; for(int i=19;i>=0;i--) { if(k>>i&1) { x=fa[x][i]; } } if(x==y)return x; for(int i=19;i>=0;i--) { if(fa[x][i]!=fa[y][i]) { x=fa[x][i];y=fa[y][i]; } } return fa[x][0]; } int main() { init(); scanf("%d %d",&n,&m); char op[5]; int le; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { scanf("%s %d",op,&le); edge tmp; if(op[0]=='D') { tmp.u=(i-1)*m+j; tmp.v=tmp.u+m; tmp.l=le; st.insert(tmp); } scanf("%s %d",op,&le); if(op[0]=='R') { tmp.u=(i-1)*m+j; tmp.v=tmp.u+1; tmp.l=le; st.insert(tmp); } } } int cnt=n*m-1; while(cnt) { edge e=*st.begin(); st.erase(st.begin()); int fu=find(e.u),fv=find(e.v); if(fu!=fv) { // cout<<e.l<<endl; f[fu]=fv; cnt--; g[e.u].pb(e.v); g[e.v].pb(e.u); } } dfs(1,0,0); for(int i=1;i<20;i++) { for(int j=1;j<=n*m;j++) { fa[j][i]=fa[fa[j][i-1]][i-1]; } } int q,x,y,_x,_y; scanf("%d",&q); while(q--) { scanf("%d %d %d %d",&x,&y,&_x,&_y); int p1=(x-1)*m+y,p2=(_x-1)*m+_y; int ff=lca(p1,p2); printf("%d ",dep[p1]+dep[p2]-2*dep[ff]); } return 0; }