学长的题。
考虑到全都变成 \(0\) 相当于从矩形外的左上部分区域直接到达矩形中的位置。
将问题转化为：从 \((0,0)\) 到 \((n,m)\)，最多跳 \(w\) 步，最少危险值。
设 \(f(i,j,k)\) 表示到 \((i,j)\) 时经过 \(k\) 个矩形。
于是就有了两种转移。当然，第二种转移可以用线段树做，但可以被卡。
还有更好的方法。考虑使用堆维护。
由于转移区域有两段，所以开两种堆分别处理。
\(qx[i][k]\) 表示所有横坐标为 \(i\) 的竖直外框区域的 \(\min\{f(i,j,k)\}\) 的集合。
\(qy[j][k]\) 同理。
用 \(mn1[i][k]、mn2[i][k]\) 来表示第 \(i\) 个矩形外框的信息。
然后动态更新即可。
注意 \(k\) 要从大往小枚举，否则可能会导致 \(f(i,j,k-1)\rightarrow f(i,j,k)\) 的情况。
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
char buf[1<<14],*p1=buf,*p2=buf;
#define GetC() ((p1==p2)&&(p2=(p1=buf)+fread(buf,1,1<<14,stdin),p1==p2)?EOF:*p1++)
struct Ios{}io;
template <typename _tp>
Ios &operator >>(Ios &in,_tp &x){
x=0;int w=0;char c=GetC();
for(;!isdigit(c);w|=c=='-',c=GetC());
for(;isdigit(c);x=x*10+(c^'0'),c=GetC());
if(w) x=-x;
return in;
}
using ll=long long;
const int N=205,M=105;
int d[N][N];
ll dp[N][N][M];
int ax[N],ay[N],bx[N],by[N];
vector<ll> v1[N][N],v2[N][N];
#define pb push_back
struct qwq{int lim;ll s;};
bool operator <(qwq x,qwq y){return x.s>y.s;}
priority_queue<qwq> qx[N][M],qy[N][M];
ll mn1[N][M],mn2[N][M];
int main(){
int n,m,_,w;io>>n>>m>>_>>w;
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
io>>d[i][j];
memset(mn1,0x3f,sizeof(mn1));
memset(mn2,0x3f,sizeof(mn2));
for(int i=1;i<=_;++i){
io>>ax[i]>>bx[i]>>ay[i]>>by[i];
if(ax[i]==1&&ay[i]==1){
for(int j=ax[i];j<=bx[i];++j)
for(int k=0;k<=w;++k) qx[j][k].push((qwq){by[i],0});
for(int j=ay[i];j<=by[i];++j)
for(int k=0;k<=w;++k) qy[j][k].push((qwq){bx[i],0});
}
for(int j=ax[i];j<=bx[i];++j) v1[j][ay[i]-1].pb(i);
for(int j=ay[i];j<=by[i];++j) v2[ax[i]-1][j].pb(i);
}
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
for(int k=w;~k;--k){
if(i!=1&&j!=1) dp[i][j][k]=d[i][j]+min(dp[i-1][j][k],dp[i][j-1][k]);
else if(j!=1) dp[i][j][k]=d[i][j]+dp[i][j-1][k];
else if(i!=1) dp[i][j][k]=d[i][j]+dp[i-1][j][k];
else dp[i][j][k]=d[i][j];
while(!qx[i][k-1].empty()&&qx[i][k-1].top().lim<j) qx[i][k-1].pop();
while(!qy[j][k-1].empty()&&qy[j][k-1].top().lim<i) qy[j][k-1].pop();
if(k>0){
if(!qx[i][k-1].empty()) dp[i][j][k]=min(dp[i][j][k],qx[i][k-1].top().s);
if(!qy[j][k-1].empty()) dp[i][j][k]=min(dp[i][j][k],qy[j][k-1].top().s);
}
for(auto tmp:v1[i][j]){
mn1[tmp][k]=min(mn1[tmp][k],dp[i][j][k]);
qx[i][k].push((qwq){by[tmp],mn1[tmp][k]});
}
for(auto tmp:v2[i][j]){
mn2[tmp][k]=min(mn2[tmp][k],dp[i][j][k]);
qy[j][k].push((qwq){bx[tmp],mn2[tmp][k]});
}
}
}
}
ll ans=1e18;
for(int i=0;i<=w;++i) ans=min(ans,dp[n][m][i]);
printf("%lld\n",ans);
return 0;
}