题解（含注释）

#include<bits/stdc++.h>
using namespace std;

// 方向数组：上、下、左、右
const int dx[] = {-1,1,0,0};
const int dy[] = {0,0,-1,1};
const long long INF = 1e18;

int n,m,K;  // n:行数, m:列数, K:最大允许的"高消耗"步数
vector<string> grid;  // 网格图，'.'表示可通过
vector<vector<int>> h;  // 每个格子的高度
int sx,sy,tx,ty;  // 起点(sx,sy)和终点(tx,ty)

/**
 * 检查在给定的高度差阈值mid下，是否能从起点到终点
 * 且"高消耗"步数不超过K
 * @param mid 允许的最大高度差（超过则消耗为1）
 * @return true-可达且消耗≤K, false-不可达或消耗>K
 */
bool ie(int mid){
    vector<vector<long long>> dist(n,vector<long long>(m,INF));
    deque<pair<int,int>> q;  // 双端队列，用于0-1 BFS
    
    dist[sx][sy] = 0;
    q.emplace_back(sx,sy);
    
    while(!q.empty()){
        auto[x,y] = q.front();
        q.pop_front();
        
        // 到达终点，检查是否满足K的限制
        if(x == tx && y == ty){
            return dist[x][y] <= K;
        }
        
        // 向四个方向扩展
        for(int d = 0; d < 4; d++){
            int nx = x + dx[d];
            int ny = y + dy[d];
            
            // 越界检查
            if(nx < 0 || nx >= n || ny < 0 || ny >= m){
                continue;
            }
            
            // 障碍物检查
            if(grid[nx][ny] != '.'){
                continue;
            }
            
            // 计算高度差
            int diff = abs(h[x][y] - h[nx][ny]);
            // 如果高度差超过mid，则这一步消耗为1，否则为0
            long long cost = (diff > mid) ? 1 : 0;
            long long nk = dist[x][y] + cost;
            
            // 如果累计消耗已经超过K，则不再考虑这个方向
            if(nk > K){
                continue;
            }
            
            // 如果找到更短路径，更新距离
            if(nk < dist[nx][ny]){
                dist[nx][ny] = nk;
                // 0-1 BFS优化：0消耗加到队首，1消耗加到队尾
                if(cost == 0){
                    q.emplace_front(nx,ny);
                }else{
                    q.emplace_back(nx,ny);
                }
            }
        }
    }
    
    // 最终检查终点是否可达且消耗≤K
    return dist[tx][ty] <= K;
}

int main(){
    // 输入处理
    cin >> n >> m >> K;
    grid.resize(n);
    for(int i = 0; i < n; i++){
        cin >> grid[i];
    }
    
    h.resize(n, vector<int>(m));
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> h[i][j]; 
        }
    }
    
    cin >> sx >> sy >> tx >> ty;
    sx--, sy--, tx--, ty--;  // 转换为0-based索引
    
    // 起点和终点相同的情况
    if(sx == tx && sy == ty){
        cout << 0;
        return 0;
    }
    
    // 计算所有相邻可通过格子之间的最大高度差
    int mf = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(grid[i][j] != '.'){
                continue;
            }
            for(int d = 0; d < 4; d++){
                int ni = i + dx[d];
                int nj = j + dy[d];
                if(ni < 0 || ni >= n || nj < 0 || nj >= m){
                    continue;
                }
                if(grid[ni][nj] != '.'){
                    continue;
                }
                mf = max(mf, abs(h[i][j] - h[ni][nj]));
            }
        }
    }
    
    // 检查最大高度差下是否可达（可行性检查）
    if(!ie(mf)){
        cout << -1;
        return 0;
    }
    
    // 二分查找最小的高度差阈值
    int left = 0, right = mf;
    int ans = mf;  // 初始化答案为最大高度差
    
    while(left <= right){
        int mid = left + (right - left) / 2;
        
        if(ie(mid)){
            // 如果mid可行，尝试更小的值
            ans = mid;
            right = mid - 1;
        }else{
            // 如果mid不可行，需要更大的值
            left = mid + 1;
        }
    }
    
    cout << ans;
    return 0;
}