LA3029最大子矩阵
最大 矩阵
2023-09-11 14:14:00 时间
题意:
给你一个n*m的矩阵<每个格子不是'F'就是'R'>,让你找一个最大的'F'矩阵,输出他的面积*3。
思路:
比较经典的题目了,现在想起来比较好想,以前的话想着很费劲,最早先用瓶颈法在杭电上过了一个数据范围比较小的,今天的这个目测瓶颈法过不去,瓶颈法的时间复杂度是O(n^3)的,今天的这个我们可以用另外一个也是比较经典的一个方法,时间复杂度是O(n^2),思路是我们可以枚举每个矩形向上延伸的最大距离,然后把这个最大距离(竖线)像左的最大平移距离和向右的最大平移距离求出来,高H[i][j],左最大距离L[i][j] ,右最大平移距离R[i][j],然后当前答案是 now = (L[i][j] + R[i][j] - 1) * H[i][j].这个很容易理解,每一个最大的子举行一定是某一个点的最长向上距离*左右活动范围得来的。然后对于更新的时候是这样的:
如果当前是'R'那么H[i][j] = 0 ,否则H[i][j] = H[i-1][j] + 1
如果当前是'R'那么L[i][j] = 0 ,否则如果当前的上一个是'R'或者当前是第一行,那么L[i][j] = ls ,否则L[i][j] = min(ls ,L[i-1][j]);ls 是当前行前面的最大延续长度,更新R[i][j]的时候类似,具体细节看代码。
#include<stdio.h>
#include<string.h>
#define N 1000 + 5
int map[N][N];
int H[N][N] ,L[N][N] ,R[N][N];
int minn(int x ,int y)
{
return x < y ? x : y;
}
int maxx(int x ,int y)
{
return x > y ? x : y;
}
int main()
{
int t ,n ,m ,i ,j;
int ls ,rs;
char str[5];
scanf("%d" ,&t);
while(t--)
{
scanf("%d %d" ,&n ,&m);
for(i = 1 ;i <= n ;i ++)
for(j = 1 ;j <= m ;j ++)
{
scanf("%s" ,str);
map[i][j] = (str[0] == 'F');
}
int Ans = 0;
memset(H ,0 ,sizeof(H));
memset(L ,0 ,sizeof(L));
memset(R ,0 ,sizeof(R));
for(i = 1 ;i <= n ;i ++)
{
for(j = 1 ;j <= m ;j ++)
if(map[i][j]) H[i][j] = H[i-1][j] + 1;
else H[i][j] = 0;
ls = 0;
for(j = 1 ;j <= m ;j ++)
{
map[i][j] ? ls ++ : ls = 0;
map[i][j] ? ((i == 1 || !map[i-1][j]) ? L[i][j] = ls : L[i][j] = minn(ls ,L[i-1][j])) : L[i][j] = 0;
}
rs = 0;
for(j = m ;j >= 1 ;j --)
{
map[i][j] ? rs ++ : rs = 0;
map[i][j] ? ((i == 1 || !map[i-1][j]) ? R[i][j] = rs : R[i][j] = minn(rs ,R[i-1][j])) : R[i][j] = 0;
if(map[i][j])
{
int now = (L[i][j] + R[i][j] - 1) * H[i][j];
if(Ans < now) Ans = now;
}
}
}
printf("%d\n" ,Ans * 3);
}
return 0;
}
给你一个n*m的矩阵<每个格子不是'F'就是'R'>,让你找一个最大的'F'矩阵,输出他的面积*3。
思路:
比较经典的题目了,现在想起来比较好想,以前的话想着很费劲,最早先用瓶颈法在杭电上过了一个数据范围比较小的,今天的这个目测瓶颈法过不去,瓶颈法的时间复杂度是O(n^3)的,今天的这个我们可以用另外一个也是比较经典的一个方法,时间复杂度是O(n^2),思路是我们可以枚举每个矩形向上延伸的最大距离,然后把这个最大距离(竖线)像左的最大平移距离和向右的最大平移距离求出来,高H[i][j],左最大距离L[i][j] ,右最大平移距离R[i][j],然后当前答案是 now = (L[i][j] + R[i][j] - 1) * H[i][j].这个很容易理解,每一个最大的子举行一定是某一个点的最长向上距离*左右活动范围得来的。然后对于更新的时候是这样的:
如果当前是'R'那么H[i][j] = 0 ,否则H[i][j] = H[i-1][j] + 1
如果当前是'R'那么L[i][j] = 0 ,否则如果当前的上一个是'R'或者当前是第一行,那么L[i][j] = ls ,否则L[i][j] = min(ls ,L[i-1][j]);ls 是当前行前面的最大延续长度,更新R[i][j]的时候类似,具体细节看代码。
#include<stdio.h>
#include<string.h>
#define N 1000 + 5
int map[N][N];
int H[N][N] ,L[N][N] ,R[N][N];
int minn(int x ,int y)
{
return x < y ? x : y;
}
int maxx(int x ,int y)
{
return x > y ? x : y;
}
int main()
{
int t ,n ,m ,i ,j;
int ls ,rs;
char str[5];
scanf("%d" ,&t);
while(t--)
{
scanf("%d %d" ,&n ,&m);
for(i = 1 ;i <= n ;i ++)
for(j = 1 ;j <= m ;j ++)
{
scanf("%s" ,str);
map[i][j] = (str[0] == 'F');
}
int Ans = 0;
memset(H ,0 ,sizeof(H));
memset(L ,0 ,sizeof(L));
memset(R ,0 ,sizeof(R));
for(i = 1 ;i <= n ;i ++)
{
for(j = 1 ;j <= m ;j ++)
if(map[i][j]) H[i][j] = H[i-1][j] + 1;
else H[i][j] = 0;
ls = 0;
for(j = 1 ;j <= m ;j ++)
{
map[i][j] ? ls ++ : ls = 0;
map[i][j] ? ((i == 1 || !map[i-1][j]) ? L[i][j] = ls : L[i][j] = minn(ls ,L[i-1][j])) : L[i][j] = 0;
}
rs = 0;
for(j = m ;j >= 1 ;j --)
{
map[i][j] ? rs ++ : rs = 0;
map[i][j] ? ((i == 1 || !map[i-1][j]) ? R[i][j] = rs : R[i][j] = minn(rs ,R[i-1][j])) : R[i][j] = 0;
if(map[i][j])
{
int now = (L[i][j] + R[i][j] - 1) * H[i][j];
if(Ans < now) Ans = now;
}
}
}
printf("%d\n" ,Ans * 3);
}
return 0;
}
相关文章
- Java实现 LeetCode 85 最大矩形
- 文本框到最大长度时跳到下一个文本框
- 【阿里云资讯】服务超2000家金融机构 阿里云成金融行业最大云服务商
- (算法)最大子数组和以及最大子矩阵和
- (剑指Offer)面试题12:打印1到最大的n位数
- loadrunner11:修改参数化表格中最大100行设置
- LeetCode-1139. 最大的以 1 为边界的正方形【前缀和,矩阵】
- 编程笔试(解析及代码实现):从矩阵中寻找和最大的子矩阵(首先需要将一个列表转为一个方矩阵)
- 智能算法应用:基于灰狼优化的最大熵图像多阈值分割 - 附代码
- 动态规划最大利润的问题
- 习题 8.10 将一个5*5的矩阵中最大的元素放在中心,4个角分别放4个最小的元素(顺序为从左到右,从上到下依次从小到大存放),写一函数实现之。用main函数调用。
- 第十三届蓝桥杯JavaB组省赛F题——最大子矩阵 (AC)