【题解】最大子矩阵

题意

给你一个的矩阵，其子矩阵的价值为该子矩阵四个角上数字中的最小值，请你求出子矩阵价值中的最大值。

题解

考虑记录下每个元素的坐标和价值，然后对从大到小排序。因为我们要最大价值的子矩阵，所以排序后从按排序的结果去找子矩阵。我们记录下每个相同行点，他们列所构成的元组。即能构成这样的元组。因为是在矩阵当中的点来构成元组的，所以只有不同行的点才会出现相同列构成的元组。所以我们按顺序遍历点以及构成元组，若在构成元组的过程中出现了之前已经构造过的元组，这说明能形成一个矩阵。此时我们所遍历的点的即是答案。

复杂度

时间复杂度

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+5;
struct node
{
    int x,y,v;
} p[N*N];
int vis[N][N];
vector<int> v[N];
bool cmp(node a,node b)
{
    return a.v>b.v;
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    int cnt=0;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
        {
            p[cnt].x=i;
            p[cnt].y=j;
            scanf("%d",&p[cnt++].v);
        }
    sort(p,p+n*m,cmp);
    for(int i=0; i<cnt; i++)
    {
        for(vector<int>::iterator it=v[p[i].x].begin(); it!=v[p[i].x].end(); it++)
        {
            if(vis[p[i].y][*it])
            {
                printf("%d",p[i].v);
                return 0;
            }
            vis[p[i].y][*it]=vis[*it][p[i].y]=1;
        }
        v[p[i].x].push_back(p[i].y);
    }
    return 0;
}