Milking Grid
Problem's Link：http://poj.org/problem?id=2185
Mean:
给你一个n*m的字符矩阵，让你求这个字符矩阵的最小覆盖矩阵，输出这个最小覆盖矩阵的面积。
analyse:
做了上一篇博客的题目，就会求一个字符串的最小覆盖矩阵。同样的，现在求字符矩阵的最小覆盖矩阵，只是将一维推向了二维，我们在纸上画一下图，你会发现，其实二维的也是so easy!
我们将每一行的字符串的最小覆盖子串求出来，然后对这n个数求LCM,那么结果就是行覆盖的最小覆盖子串；同样的我们再对每一列求最小覆盖子串，然后对这m个数求LCM，那么结果就是列覆盖的最小覆盖子串。
最后的答案：area=两个数的乘积。
Time complexity：O(n*m)
Source code：
// Memory Time // 1347K 0MS // by : Snarl_jsb // 2014-10-03-20.59 #include<algorithm> #include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<vector> #include<queue> #include<stack> #include<map> #include<string> #include<climits> #include<cmath> #define N 1000010 #define LL long long using namespace std; char str[10010][100],tmp[10010]; int row[10010],col[100]; vector<int> next; void GetNext(char str[]) { // puts(str); next.clear(); next.push_back(0); int len=strlen(str); int k=0; for(int i=1;i<len;++i) { while(k!=0&&str[i]!=str[k]) k=next[k-1]; if(str[i]==str[k]) k++; next.push_back(k); } // for(int i=0;i<len;++i) // cout<<next[i]<<endl; } int gcd(int a,int b) { return b==0?a:gcd(b,a%b); } int lcm(int a,int b) { return a*b/gcd(a,b); } int main() { ios_base::sync_with_stdio(false); cin.tie(0); // freopen("C:\\Users\\ASUS\\Desktop\\cin.cpp","r",stdin); // freopen("C:\\Users\\ASUS\\Desktop\\cout.cpp","w",stdout); int r,c; cin>>r>>c; for(int i=0;i<r;++i) { scanf("%s",str[i]); } int len; len=c; for(int i=0;i<r;++i) { GetNext(str[i]); row[i]=len-next[len-1] ; } len=r; for(int i=0;i<c;++i)//列 { for(int j=0;j<r;++j)//行 { tmp[j]=str[j][i]; } GetNext(tmp); col[i]=len-next[len-1]; } int r1=row[0]; for(int i=1;i<r;++i) { r1=lcm(r1,row[i]); if(r1>c) { r1=c; break; } } int c1=col[0]; for(int i=1;i<c;++i) { c1=lcm(c1,col[i]); if(c1>r) { c1=r; break; } } // cout<<r1<<endl; // cout<<c1<<endl; cout<<r1*c1<<endl; return 0; }
