题目要求最小化爬楼梯的次数，那么我们就要让楼层的变化尽量小，即沿线楼房高度越高越好。不难发现影响答案的是路线中的楼房高度的最小值，则需要最大化最小值。那么就不难用 Kruskal 重构树做了。对每个点进行唯一编号，相邻的点建边权为较小的的楼房高度的双向边。剩下的就是 Kruskal 的模板了。最后求解答案时有一些细节，详见代码。
时间复杂度 \(O(nm\log nm+q\log^2 nm)\)，当然如果使用倍增代替树链剖分，则可以做到 \(O((nm+q)\log nm)\)。
#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
#define N 1000001using namespace std;vector<int> G[N];
int n,m,a[1001][1001],fa[N],cnt,cnt1,hd[N],b[N],node;
int top[N],siz[N],son[N],t[N * 4],dep[N],ans,id[N],rev[N],tot;int getid( int i , int j )
{return ( i - 1 ) * m + j;
}struct E
{int v,w,nxt;
}e[N * 2];struct E1
{int u,v,w;
}e1[N * 2];void addedge( int u , int v , int w )
{cnt ++;e[cnt].v = v;e[cnt].w = w;e[cnt].nxt = hd[u];hd[u] = cnt;}void add( int u , int v , int w )
{addedge( u , v , w );addedge( v , u , w );cnt1 ++;e1[cnt1] = { u , v , w };
}bool cmp( E1 x , E1 y )
{return x.w > y.w;
}int cx( int x )
{if( x == fa[x] ) return x;return fa[x] = cx( fa[x] );
}void dfs1( int u , int ff )
{fa[u] = ff;dep[u] = dep[ff] + 1;siz[u] = 1;for( auto v : G[u] ){if( v == ff ) continue;dfs1( v , u );siz[u] += siz[v];if( siz[v] > siz[son[u]] )son[u] = v;}
}void dfs2( int u , int ff , int flag )
{id[u] = ++ tot;rev[tot] = u;if( flag ) top[u] = u;else top[u] = top[ff];if( son[u] ) dfs2( son[u] , u , 0 );for( auto v : G[u] ){if( v == ff || v == son[u] ) continue;dfs2( v , u , 1 );}
}void build( int u , int l , int r )
{if( l == r ){t[u] = b[rev[l]];return;}int mid = ( l + r ) >> 1;build( u << 1 , l , mid );build( u << 1 | 1 , mid + 1 , r );t[u] = min( t[u << 1] , t[u << 1 | 1] );
}int query( int u , int l , int r , int L , int R )
{if( L <= l && r <= R ) return t[u];int mid = ( l + r ) >> 1,mi = 10000000;if( L <= mid ) mi = min( mi , query( u << 1 , l , mid , L , R ) );if( R > mid ) mi = min( mi , query( u << 1 | 1 , mid + 1 , r , L , R ) );return mi;
}int que( int u , int v )
{int mi = 10000000;while( top[u] != top[v] ){if( dep[top[u]] > dep[top[v]] ) swap( u , v );mi = min( mi , query( 1 , 1 , node , id[top[v]] , id[v] ) );v = fa[top[v]];}if( dep[u] > dep[v] ) swap( u , v );mi = min( mi , query( 1 , 1 , node , id[u] , id[v] ) );return mi;
}int main()
{cin >> n >> m;for( int i = 1 ; i <= n ; i ++ )for( int j = 1 ; j <= m ; j ++ )cin >> a[i][j],b[getid( i , j )] = a[i][j];for( int i = 1 ; i <= n ; i ++ )for( int j = 1 ; j <= m ; j ++ ){if( i - 1 >= 1 ) add( getid( i - 1 , j ) , getid( i , j ) , min( a[i - 1][j] , a[i][j] ) );if( i + 1 <= n ) add( getid( i + 1 , j ) , getid( i , j ) , min( a[i + 1][j] , a[i][j] ) );if( j - 1 >= 1 ) add( getid( i , j - 1 ) , getid( i , j ) , min( a[i][j - 1] , a[i][j] ) );if( j + 1 <= m ) add( getid( i , j + 1 ) , getid( i , j ) , min( a[i][j + 1] , a[i][j] ) );}sort( e1 + 1 , e1 + cnt1 + 1 , cmp );for( int i = 1 ; i <= n * m * 2 ; i ++ )fa[i] = i;node = n * m;int u,v;for( int i = 1 ; i <= cnt1 ; i ++ ){u = e1[i].u,v = e1[i].v;if( cx( u ) == cx( v ) ) continue;node ++;b[node] = e1[i].w;G[node].push_back( cx( u ) );G[node].push_back( cx( v ) );fa[cx( u )] = fa[cx( v )] = node;// cout << u << ' ' << v << ' ' << e1[i].w << '\n';}// cout << node << '\n';dfs1( node , 0 );dfs2( node , 0 , 1 );build( 1 , 1 , node );int q,x1,y1,x2,y2,h1,h2,dd;cin >> q;while( q -- ){cin >> x1 >> y1 >> h1 >> x2 >> y2 >> h2;u = getid( x1 , y1 ),v = getid( x2 , y2 );// cout << u << ' ' << v << '\n';ans = 0;if( h1 > h2 ) ans += h1 - h2,h1 = h2;//比较起点与终点高度dd = que( u , v );if( dd < h1 ) ans += h1 - dd,h1 = dd;//判断沿线是否需要向下下楼ans += abs( h1 - h2 );//到达终点cout << ans << '\n';}return 0;
}