首页 > 代码库 > HDU 2870 Largest Submatrix (单调栈)
HDU 2870 Largest Submatrix (单调栈)
http://acm.hdu.edu.cn/showproblem.php?
pid=2870
Largest SubmatrixTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 1569 Accepted Submission(s): 748
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
2 4 abcw wxyz
Sample Output
3
Source
2009 Multi-University Training Contest 7 - Host by FZU
矩阵中有7种字母:abcwxyz,w可替换为a或b,x可替换为b或c,y可替换为a或c,z可替换为a、b或c。求一个子矩阵,该矩阵中全部元素都同样,问该矩阵最大是多少?
分析:
首先将w,x,y,z换为a,b,c;得到3个01矩阵。然后就是求元素所有是1的最大子矩阵,能够转化为面积做。
维护出第i行各元素的“高度”,然后用单调栈向左/右找到比该点低的位置并记录,最后计算面积。
/* * * Author : fcbruce <fcbruce8964@gmail.com> * * Time : Sat 25 Oct 2014 07:10:43 PM CST * */ #include <cstdio> #include <iostream> #include <sstream> #include <cstdlib> #include <algorithm> #include <ctime> #include <cctype> #include <cmath> #include <string> #include <cstring> #include <stack> #include <queue> #include <list> #include <vector> #include <map> #include <set> #define sqr(x) ((x)*(x)) #define LL long long #define itn int #define INF 0x3f3f3f3f #define PI 3.1415926535897932384626 #define eps 1e-10 #ifdef _WIN32 #define lld "%I64d" #else #define lld "%lld" #endif #define maxm #define maxn 1007 using namespace std; int trans[maxn][maxn][3]; char matrix[maxn][maxn]; int n,m; int ql[maxn],qr[maxn],fl,rl,fr,rr; int h[maxn]; int l[maxn],r[maxn]; inline void init(int x,int y,char ch) { switch (ch) { case 'a': trans[x][y][0]=1; break; case 'b': trans[x][y][1]=1; break; case 'c': trans[x][y][2]=1; break; case 'w': trans[x][y][0]=trans[x][y][1]=1; break; case 'x': trans[x][y][1]=trans[x][y][2]=1; break; case 'y': trans[x][y][0]=trans[x][y][2]=1; break; case 'z': trans[x][y][0]=trans[x][y][1]=trans[x][y][2]=1; break; } } int solve(int k) { int MAX=0; memset(h,0,sizeof h); for (int i=0;i<n;i++) { for (int j=0;j<m;j++) { if (trans[i][j][k]==1) h[j]++; else h[j]=0; } fl=fr=0;rl=rr=-1; for (int j=0;j<m;j++) { while (fl<=rl && h[ql[rl]]>=h[j]) rl--; if (fl<=rl) l[j]=ql[rl]+1; else l[j]=0; ql[++rl]=j; while (fr<=rr && h[qr[rr]]>=h[m-j-1]) rr--; if (fr<=rr) r[m-j-1]=qr[rr]; else r[m-j-1]=m; qr[++rr]=m-j-1; } for (int j=0;j<m;j++) MAX=max(MAX,h[j]*(r[j]-l[j])); } return MAX; } int main() { #ifdef FCBRUCE freopen("/home/fcbruce/code/t","r",stdin); #endif // FCBRUCE while (scanf("%d%d",&n,&m)==2) { for (int i=0;i<n;i++) scanf("%s",matrix[i]); memset(trans,0,sizeof trans); for (int i=0;i<n;i++) for (int j=0;j<m;j++) init(i,j,matrix[i][j]); int MAX=0; for (int i=0;i<3;i++) MAX=max(MAX,solve(i)); printf("%d\n",MAX); } return 0; }
HDU 2870 Largest Submatrix (单调栈)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。