分析

类似于点分治的思想，只统计经过分割线的最短路，然后把地图一分为二。

代码

#include <bits/stdc++.h>
#define rin(i,a,b) for(register int i=(a);i<=(b);++i)
#define irin(i,a,b) for(register int i=(a);i>=(b);--i)
#define trav(i,a) for(register int i=head[a];i;i=e[i].nxt)
typedef long long LL;
using std::cin;
using std::cout;
using std::endl;

inline int read(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

const int MAXN=200005;

int n,m,q,*r[MAXN],*c[MAXN],ans[MAXN];
int dis[MAXN];
int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};
bool vis[MAXN];

struct Qu{
    int sx,sy,tx,ty,id;
}a[MAXN],b[MAXN];

struct Pair{
    int pos,dis;
    inline friend bool operator > (Pair x,Pair y){
        return x.dis>y.dis;
    }
};

std::priority_queue<Pair,std::vector<Pair>,std::greater<Pair> > pq;

inline int id(int x,int y){
    return (x-1)*m+y;
} 

void dijkstra(int sx,int sy,int sn,int tn,int sm,int tm){
    rin(i,sn,tn) rin(j,sm,tm) dis[id(i,j)]=1e9,vis[id(i,j)]=false;
    while(!pq.empty()) pq.pop();
    dis[id(sx,sy)]=0;
    pq.push((Pair){id(sx,sy),0});
    while(!pq.empty()){
        int idx=pq.top().pos;pq.pop();
        if(vis[idx]) continue;
        vis[idx]=true;
        int x=(idx-1)/m+1,y=idx-(x-1)*m;
        rin(i,0,3){
            int xx=x+dx[i],yy=y+dy[i],w=0;
            if(xx<sn||xx>tn||yy<sm||yy>tm||vis[id(xx,yy)]) continue;
            if(i==0) w=c[xx][yy];
            else if(i==1) w=c[x][y];
            else if(i==2) w=r[xx][yy];
            else w=r[x][y];
            if(dis[id(xx,yy)]>dis[idx]+w){
                dis[id(xx,yy)]=dis[idx]+w;
                pq.push((Pair){id(xx,yy),dis[id(xx,yy)]});
            }
        }
    }
}

void solve(int sn,int tn,int sm,int tm,int sq,int tq){
    if(sn>tn||sm>tm||sq>tq) return;
    if(tn-sn<tm-sm){
        int mid=((sm+tm)>>1);
        rin(i,sn,tn){
            dijkstra(i,mid,sn,tn,sm,tm);
            rin(j,sq,tq){
                ans[a[j].id]=std::min(ans[a[j].id],
                dis[id(a[j].sx,a[j].sy)]+dis[id(a[j].tx,a[j].ty)]);
            }
        }
        int top=0;
        rin(i,sq,tq) if(a[i].sy<mid&&a[i].ty<mid) b[++top]=a[i];
        int temp=top;
        rin(i,sq,tq) if(a[i].sy>mid&&a[i].ty>mid) b[++top]=a[i];
        memcpy(a+sq,b+1,top*sizeof(Qu));
        solve(sn,tn,sm,mid-1,sq,sq+temp-1);
        solve(sn,tn,mid+1,tm,sq+temp,sq+top-1);
    }
    else{
        int mid=((sn+tn)>>1);
        rin(i,sm,tm){
            dijkstra(mid,i,sn,tn,sm,tm);
            rin(j,sq,tq){
                ans[a[j].id]=std::min(ans[a[j].id],
                dis[id(a[j].sx,a[j].sy)]+dis[id(a[j].tx,a[j].ty)]);
            }
        }
        int top=0;
        rin(i,sq,tq) if(a[i].sx<mid&&a[i].tx<mid) b[++top]=a[i];
        int temp=top;
        rin(i,sq,tq) if(a[i].sx>mid&&a[i].tx>mid) b[++top]=a[i];
        memcpy(a+sq,b+1,top*sizeof(Qu));
        solve(sn,mid-1,sm,tm,sq,sq+temp-1);
        solve(mid+1,tn,sm,tm,sq+temp,sq+top-1);
    }
}

int main(){
    n=read(),m=read();
    rin(i,1,n) r[i]=new int [m+5],c[i]=new int [m+5];
    rin(i,1,n) rin(j,1,m-1) r[i][j]=read();
    rin(i,1,n-1) rin(j,1,m) c[i][j]=read();
    q=read();
    rin(i,1,q){
        a[i].sx=read();
        a[i].sy=read();
        a[i].tx=read();
        a[i].ty=read();
        a[i].id=i;
        ans[i]=1e9;
    }
    solve(1,n,1,m,1,q);
    rin(i,1,q) printf("%d\n",ans[i]);
    return 0;
}