Minimax Gym - 101972G （思维+维护子矩阵的最值）

You are given a grid consisting of n rows each of which is dived into m columns. The rows are numbered from 1 to n from top to bottom, and the columns are numbered from 1 to m from left to right. Each cell is identified by a pair (x, y), which means that the cell is located in the row x and column y.

Your goal is to delete a row x (1 < x < n) and a column y (1 < y < m), after this the matrix will be divided into 4 parts. Let us define the beauty of each part as the maximum value inside it. Your task is to choose x and y such that the difference between the largest and smallest beauties is as minimal as possible. Can you?

Input

The first line contains an integer T (1 ≤ T ≤ 100) specifying the number of test cases.

The first line of each test case contains two integers n and m (3 ≤ n, m ≤ 500), specifying the grid size, in which n is the number of rows and m is the number of columns.

Then n lines follow, each line contains m integers, giving the grid. All values in the grid are between 1 and 109 (inclusive).

Output

For each test case, print a single line containing the minimum difference between the largest and smallest beauties after dividing the matrix into 4 parts.

Example

Input

2
3 3
9 5 8
3 4 1
6 2 7
4 4
22 7 3 11
3 1 8 9
5 2 4 3
13 5 6 9

Output

3
13

 题意：给你一个矩阵，然后一种操作，选择一个非边界点，去掉该点所在的列和行，肯定会剩下四部分，求这四部分中的最大值的最大值减去最大值的最小值，使得这个差最小

比如：一次操作之后，第一部分的最大值是3，第二部分是7，第三部分是5，第四部分是11；

所以这个差就是11-3=7；

思路：枚举每个可以操作的点，然后取最小值就行了

前提是得维护一下每个子矩阵的最值；

废话不多说，具体看代码： 

#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;

const int maxn=505;
const int INF=0x3f3f3f3f;
int ans,n,m;
int a1[maxn][maxn],a2[maxn][maxn],a3[maxn][maxn],a4[maxn][maxn],mm[maxn][maxn];
int main()
{
    int T;
    scanf(\"%d\",&T);
    while(T--)
    {
        memset(a1,0,sizeof(a1));
        memset(a2,0,sizeof(a2));
        memset(a3,0,sizeof(a3));
        memset(a4,0,sizeof(a4));
        ans=INF;
        scanf(\"%d%d\",&n,&m);
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                scanf(\"%d\",&mm[i][j]);
                a1[i][j]=a2[i][j]=a3[i][j]=a4[i][j]=mm[i][j];
            }
        }
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                a1[i][j]=max(max(a1[i][j-1],a1[i-1][j]),a1[i][j]);
        for(int i=1;i<=n;i++)
            for(int j=m;j>=1;j--)
                a2[i][j]=max(max(a2[i][j+1],a2[i-1][j]),a2[i][j]);
        for(int i=n;i>=1;i--)
            for(int j=1;j<=m;j++)
                a3[i][j]=max(max(a3[i][j-1],a3[i+1][j]),a3[i][j]);
        for(int i=n;i>=1;i--)
            for(int j=m;j>=1;j--)
                a4[i][j]=max(max(a4[i][j+1],a4[i+1][j]),a4[i][j]);
        for(int i=2;i<n;i++)
        {
            for(int j=2;j<m;j++)
            {
                int mmm=0,nnn=INF;
                mmm=max(mmm,a1[i-1][j-1]);
                mmm=max(mmm,a2[i-1][j+1]);
                mmm=max(mmm,a3[i+1][j-1]);
                mmm=max(mmm,a4[i+1][j+1]);

                nnn=min(nnn,a1[i-1][j-1]);
                nnn=min(nnn,a2[i-1][j+1]);
                nnn=min(nnn,a3[i+1][j-1]);
                nnn=min(nnn,a4[i+1][j+1]);
                ans=min(ans,mmm-nnn);
            }
        }
        printf(\"%d\\n\",ans);
    }
	return 0;
}