给你一个矩阵,让你在里面找到一个最大的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 " ,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 " ,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 " ,ans * 3); } return 0; }