55tps蒟蒻救助

#include<bits/stdc++.h>
using namespace std;
const int maxn=2003;
int n,m,s,k,f[maxn][maxn],a[maxn][maxn];
bool check(int x,int y){
	if((a[x][y]+a[x][y+1]>0||a[x][y]+a[x][y-1]>0)&&a[x][y]>0)return 1;
	return 0;
}
void update1(int x){
	for(int y=1;y<=m;y++){
		if(f[x][y+1]>=0)f[x][y]=min(k,max(f[x][y],f[x][y+1]+a[x][y]));
		if(f[x][y-1]>=0)f[x][y]=min(k,max(f[x][y],f[x][y-1]+a[x][y]));
	}
}
void update2(int x){
	for(int y=m;y>=1;y--){
		if(f[x][y+1]>=0)f[x][y]=min(k,max(f[x][y],f[x][y+1]+a[x][y]));
		if(f[x][y-1]>=0)f[x][y]=min(k,max(f[x][y],f[x][y-1]+a[x][y]));
	}
}
int main(){
	int c,t;cin>>c>>t;
	while(t--){
		cin>>n>>m>>s>>k;
		for(int i=1;i<=m;i++)f[0][i]=s;
		for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){f[i][j]=-1e9,a[i][j]=0;}
		for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%d",&a[i][j]);
		for(int i=1;i<n;i++){
			for(int j=1;j<=m;j++){
				if(check(i,j))a[i][j]=k;
				if(f[i-1][j]>=0)f[i][j]=min(k,f[i-1][j]+a[i][j]);
			}
			update1(i);update2(i);update1(i);update2(i);update1(i);
		}
		for(int i=1;i<=m;i++)if(f[n-1][i]>=0)f[n][i]=min(k,f[n-1][i]+a[n][i]);
		int ans=-1;
		for(int i=1;i<=m;i++)ans=max(ans,f[n][i]);
		cout<<ans<<endl;
	}
	return 0;
}