思维-G. Minimax 二维区域中的最值

#include<bits/stdc++.h>
#define endl '\n'
#define _for(i,a,b) for(int i=a;i<b;i++)
using namespace std;
const int N = 505;
typedef long long ll;
int Map[N][N],D1[N][N],D4[N][N],D2[N][N],D3[N][N];
int main(){ 
    int t; cin>>t;
    while(t--){
        int n,m; 
        cin>>n>>m;
        memset( D1,0,sizeof(D1) );
        memset( D2,0,sizeof(D2) );
        memset( D3,0,sizeof(D3) );
        memset( D4,0,sizeof(D4) );

        _for(i,1,n+1){//左上角 
            _for(j,1,m+1){ 
                scanf("%d",&Map[i][j]);
                D1[i][j]=Map[i][j];
                if(j>1) D1[i][j]=max( D1[i][j] , D1[i][j-1] );
                if(i>1) D1[i][j]=max( D1[i][j] , D1[i-1][j] );
            }
        }
        for(int i= n;i>0;i--){//左下角 
            for(int j=1;j<=m;j++){
                D2[i][j]=Map[i][j];
                if(i<n) D2[i][j]=max( D2[i][j] , D2[i+1][j] );
                if(j>1) D2[i][j]=max( D2[i][j] , D2[i][j-1] );
            }
        }
        for(int i= n;i>0;i--){//右下角 
            for(int j=m;j>0;j--){
                D3[i][j]=Map[i][j];
                if(i<n) D3[i][j]=max( D3[i][j] ,  D3[i+1][j] );
                if(j<m) D3[i][j]=max( D3[i][j] , D3[i][j+1] );
            }
        }
        for(int i= 1;i<=n;i++){//右上角 
            for(int j=m;j>0;j--){
                D4[i][j]=Map[i][j];
                if(i>1) D4[i][j]=max( D4[i][j] ,  D4[i-1][j] );
                if(j<m) D4[i][j]=max( D4[i][j] , D4[i][j+1] );
            }
        }
        int res = 0x3f3f3f3f;
        _for(i,2,n){
            _for(j,2,m){
                int Max=0,Min=0x3f3f3f3f;
                Max=max(Max,D1[i-1][j-1]);
                Max=max(Max,D2[i+1][j-1]);
                Max=max(Max,D3[i+1][j+1]);
                Max=max(Max,D4[i-1][j+1]);
                Min=min(Min,D1[i-1][j-1]);
                Min=min(Min,D2[i+1][j-1]);
                Min=min(Min,D3[i+1][j+1]);
                Min=min(Min,D4[i-1][j+1]); 
                res = min(res,Max-Min );
            }
        }
        printf("%d\n",res);
    }
    return 0;
}