题意:
给你一个矩阵,让你在里面找到一个最大的f矩阵..
思路:
三种方法ac这到题目;
方法(1) 以宽为主,暴力
开一个数组sum[i][j],记录当前这个位置的前面有多少个连续的f,更新完这个数组时候在枚举每一个点,只处理最后一列或者sum[i][j+1] =0 的点,因为只有这样的点才可能是最大的,对于每一个要处理的点,直接往上跑和往下跑,跑的条件是sum[i][j] <= sum[k][j]
(k是上跑或下跑的数),然后找到一共跑了多少个,当前的最大就是 sum[i][j] * cnt(次数);
方法(2) 以高为主,暴力
开一个数组sum[j],记录第j列的前面有多少个连续的’F’,其实跟方法1差不多,只不过是节省了空间,而且非常好写,只要把方法一的矩阵旋转一下就写法一样了,不多说…
方法(3) 以高或宽为主,dp
无论是方法一还是方法二,过程中都会有这么一步就是对于当前的点,我们要找到它左边有多少个f有边有多少个f,对于找f的这个环节我们可以dp实现,开两个数组L[],R[],L[i]代表i的左边f连续到那个下标,R[i]便是i的有边的f连续到那个下标,这样就可以O(n)的时间吧所有的都找到,然后枚举找最大就行了,汉字不太好解释,直接看代码就懂了..
找宽(1)
#include<stdio.h>
#include<string.h>#define N 1000 + 10
int map[N][N];
int sum[N][N];char str[10];int main ()
{
int t ,i ,j ,n ,m;
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);
if(str[0] == 'F') map[i][j] = 1;
else map[i][j] = 0;
} for(i = 1 ;i <= n ;i ++)
{
sum[i][1] = map[i][1];
for(j = 2 ;j <= m ;j ++)
{
if(map[i][j]) sum[i][j] = sum[i][j-1] + 1;
else sum[i][j] = 0;
}
} int ans = 0;
for(i = 1 ;i <= n ;i ++)
for(j = 1 ;j <= m ;j ++)
{
if(sum[i][j] > 0 && (j == m || !sum[i][j+1]))
{
int ss = sum[i][j];
for(int k = i - 1 ;k >= 1 ;k --)
{
if(sum[k][j] < sum[i][j]) break;
ss += sum[i][j];
}
for(int k = i + 1 ;k <= n ;k ++)
{
if(sum[k][j] < sum[i][j]) break;
ss += sum[i][j];
}
if(ans < ss) ans = ss;
}
}
printf("%d\n" ,ans * 3);
}
return 0;
}
找高(2)
#include<stdio.h>
#include<string.h>#define N 1000 + 100
int sum[N];
char map[N][N];
char str[10];int main ()
{
int n ,m, i ,j ,t;
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];
} memset(sum ,0 ,sizeof(sum));
int ans = 0;
for(i = 1 ;i <= n ;i ++)
{
for(j = 1 ;j <= m ;j ++)
if(map[i][j] == 'F') sum[j]++;
else sum[j] = 0; for(j = 1 ;j <= m ;j ++)
{
if(!sum[j]) continue;
int ss = sum[j];
for(int k = 1 ;j + k <= m && sum[j+k] >= sum[j] ;k ++)
ss += sum[j];
for(int k = 1 ;j - k >= 1 && sum[j-k] >= sum[j] ;k ++)
ss += sum[j];
if(ss > ans) ans = ss;
}
}
printf("%d\n" ,ans * 3);
}
return 0;
}
找高(dp优化)(3)
#include<stdio.h>
#include<string.h>#define N 1000 + 100
int sum[N];
int L[N] ,R[N];
char map[N][N];
char str[10];int main ()
{
int n ,m, i ,j ,t;
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];
} memset(sum ,0 ,sizeof(sum));
int ans = 0;
for(i = 1 ;i <= n ;i ++)
{
for(j = 1 ;j <= m ;j ++)
if(map[i][j] == 'F') sum[j]++;
else sum[j] = 0; L[1] = 1 ,R[m] = m;
for(j = 2 ;j <= m ;j ++)
{
int k = j;
while(k > 1 && sum[j] <= sum[k-1]) k = L[k-1];
L[j] = k;
}
for(j = m - 1 ;j >= 1 ;j --)
{
int k = j;
while(k < m && sum[j] <= sum[k+1]) k = R[k+1];
R[j] = k;
}
for(j = 1 ;j <= m ; j++)
{
int now = (R[j] - L[j] + 1) * sum[j];
if(ans < now) ans = now;
} /*
for(j = 1 ;j <= m ;j ++)
{
if(!sum[j]) continue;
int ss = sum[j];
for(int k = 1 ;j + k <= m && sum[j+k] >= sum[j] ;k ++)
ss += sum[j];
for(int k = 1 ;j - k >= 1 && sum[j-k] >= sum[j] ;k ++)
ss += sum[j];
if(ss > ans) ans = ss;
}
*/
}
printf("%d\n" ,ans * 3);
}
return 0;
}
