Largest Submatrix
Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 970Accepted Submission(s): 470
Problem Description
Now here is a matrix with letter 'a','b','c','w','x','y','z' and you can change 'w' to 'a' or 'b', change 'x' to 'b' or 'c', change 'y' to 'a' or 'c', and change 'z' to 'a', 'b' or 'c'. After you changed it, what's the largest submatrix with the same letters
you can make?
Input
The input contains multiple test cases. Each test case begins with m and n (1 ≤ m, n ≤ 1000) on line. Then come the elements of a matrix in row-major order on m lines each with n letters. The input ends once EOF is met.
Output
For each test case, output one line containing the number of elements of the largest submatrix of all same letters.
Sample Input
Sample Output
此题类似求最大全1子矩阵(参考这里:http://blog.csdn.net/gaotong2055/article/details/8960118),只不过这里要分别求abc的。
#include <stdio.h>
char matrix[1001][1001];
int h[1005], left[1005], right[1001];
char ms[3][1001][1001]; // 转换后a,b,c 的矩阵
char c3[4] = "abc";
char chage(char a, char b) { //转换char a 到 char b
if (a == 'w' && (b == 'a' || b == 'b'))
return b;
if (a == 'x' && (b == 'b' || b == 'c'))
return b;
if (a == 'y' && (b == 'c' || b == 'a'))
return b;
if (a == 'z')
return b;
return a;
}
int main() {
int m, n;
//freopen("in.txt", "r", stdin);
while (scanf("%d %d", &m, &n) != EOF) {
getchar(); //读取行尾
for (int i = 0; i < m; i++) {
gets(matrix[i]);
}
int max = 0, tmp, tmax;
//循环3次),求(a,b,c)最大子矩阵
for (int k = 0; k < 3; k++) {
for (int i = 0; i < m; i++) {
for (int j = 1; j <= n; j++)
ms[k][i][j] = chage(matrix[i][j-1], c3[k]); //转换矩阵
}
//求高
for (int j = 0; j <= n; j++) {
h[j] = left[j] = right[j] = 0;
}
//求最大子面积
for (int i = 0; i < m; i++) {
for (int j = 1; j <= n; j++) {
if (ms[k][i][j] == c3[k])
h[j] += 1;
else
h[j] = 0;
}
h[0] = h[n+1] = -1;
for (int j = 1; j <= n; j++) {
tmp = j;
while (h[j] <= h[tmp - 1] ) {
tmp = left[tmp - 1] ;
}
if (tmp < 0)
tmp = 0;
left[j] = tmp;
}
// for (int j = 1; j <= n; j++)
// printf("%d ", left[j]);
// printf("\n");
for (int j = n ; j > 0; j--) {
tmp = j;
while (h[j] <= h[tmp + 1] ) {
tmp = right[tmp + 1] ;
}
right[j] = tmp;
tmax = (tmp - left[j] + 1) * h[j];
if(max < tmax){
max = tmax;
}
}
// for (int j = 1; j <= n; j++)
// printf("%d ", right[j]);
// printf("\n");
}
}
printf("%d\n",max);
}
return 0;
}
分享到:
相关推荐
For convenience, the maximum submatrix sum is 0 if all the integers are negative. Example: For matrix and has the sum of 15. 0270 9262 92 4 1 4 1 , the maximum ...
Given an n*n matrix composed of 0 or 1, determine the top left corner position and the order of the maximum submatrix in which all of element are 1. Example: Input: 5 1 1 0 1 0 1 0 1 0 1 0 1 1...
用C#做的局域网聊天系统 希望对大家有用
矩阵划分为子矩阵 将一维数组转换为二维 实现 toMatrix(data, rowSize) 函数,该函数以一个数组和一个数字为参数,并返回一个新数组。 数字表示子数组中元素的个数,子数组的元素取自数据数组。...
特征值计算的新特征向量 该存储库实现了此新,该使我们能够通过PyTorch从特征向量优雅地计算出特征向量。 我将其移植到PyTorch,...eigenvectors to the eigenvalues and the submatrix eigenvalues. 核心方程 这是核
自己写的 MATRIX 类,V0,3 版本。 定义了矩阵之间的 加,减,乘 矩阵和实数间的 加,减,乘,除 包括 LU 分解,列主元 LU 分解,Cholesky 分解 改进的 Cholesky 分解算法存在问题...A.SubMatrix(2,3,5,12);//功能同上
此块输出由元素的原始索引和列索引定义的矩阵的给定元素。Submatrix 不允许用户在块外定义索引,而这个简单块可以。
z = (|z_1|^2+|z_2|^2+\ldots+|z_k|^2)I_{n \times n}$. Define $\mathcal{O}_z$ a first type COD if and only if $\mathcal{O}_z$ does not contain submatrix $\begin{pmatrix} \pm z_j & 0<...
z = (|z_1|^2+|z_2|^2+\ldots+|z_k|^2)I_{n \times n}$. Define $\mathcal{O}_z$ a first type COD if and only if $\mathcal{O}_z$ does not contain submatrix $\begin{pmatrix} \pm z_j & 0<...