题目传送
题意:
给你一个n*n的矩阵,上面写着0到9的数字,现在问你:选取同一种数字中的任意三个,组成的三角形的最大面积 * 2是多少,每选取一种数字的时候,你最多可以改动一次,使得某个位置变成你想要的数字,在这个数字选取完后,改动的数字变回原样。
思路:
1.既然每次可以改一次,那么肯定只要存在俩个点那么三角形面积就不会为0.那么我直接枚举俩个点就是了,另外一个点配合选取的俩个点使得面积最大即可,但是暴力选取俩个点会T
2.我们知道三角形面积是 底乘高除二 ,那么既然另外一个点是我们可以控制的,可以配合俩个点达到面积最大值。那么这个俩个点我们要选取的话,什么情况下,他们可能存在最大值。
3.那么我们只需要控制这个三角形的高,然后底我们可以枚举每一个点,再控制另外一个点取最大的底。那么这个高怎么选呢?因为这个三角形的一边必须平行矩形的一边,所以我们先假设这个高平行x轴,那么我们肯定是选x最大和最小的俩个点去枚举,因为在枚举的时候,高 能达到最大值。同理假设这个高平行y轴,那么我们肯定是选y最大和最小的俩个点去枚举, 这样枚举一遍,取最大值即可
#include<bits/stdc++.h>
using namespace std;
const int N = 4e6 + 100;
char str[2005][2005];
signed main()
{
std::ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
int t;
cin >> t;
while(t--)
{
int n;
cin >> n;
for(int i = 1;i <= n;i++)
for(int j = 1;j <= n;j++)
cin >> str[i][j];
for(int num = 0;num < 10;num++)
{
int x = 0,y = 0,Max = 0,m = 0,xx = 0,yy = 0,xxx = INF,yyy = INF,xxxx = INF,yyyy = INF;
for(int i = 1;i <= n;i++)
{
for(int j = 1;j <= n;j++)
{
if(str[i][j] - '0' == num)
{
if(x < i)//x最大的点
x = i,y = j;
if(yy < j)//y最大的点
xx = i,yy = j;
if(xxx > i)//x最小的点
xxx = i,yyy = j;
if(yyyy > j)//y最小的点
yyyy = j,xxxx = i;
m++;
}
}
}
if(m < 2) {cout << 0 << " ";continue;}//如果都没有俩个点,面积为0
for(int i = 1;i <= n;i++)//枚举每一个点
{
for(int j = 1;j <= n;j++)
{
if(str[i][j] - '0' == num)
{
Max = max(Max,max(n-j,j-1)*(x-i));//另外一点任意取,所以在高固定的情况下,取最大的底
Max = max(Max,max(n-y,y-1)*(x-i));
Max = max(Max,max(n-i,i-1)*(yy-j));//上底
Max = max(Max,max(n-xx,xx-1)*(yy-j));//下底
Max = max(Max,max(n-j,j-1)*(i-xxx));
Max = max(Max,max(n-yyy,yyy-1)*(i-xxx));
Max = max(Max,max(n-i,i-1)*(j-yyyy));
Max = max(Max,max(n-xxxx,xxxx-1)*(j-yyyy));
}
}
}
cout << Max << " ";
}
cout << endl;
}
}