设为首页 加入收藏

TOP

poj2185 Milking Grid (最小覆盖矩阵)
2015-07-20 17:55:06 来源: 作者: 【 】 浏览:5
Tags:poj2185 Milking Grid 最小 覆盖 矩阵
//给定一个由字符组成的矩阵,求出它的面积最小的覆盖矩阵
//可以求出每一行的最小覆盖子串的长度,只要对这些长度求最小公倍数,就可以获得最小覆盖矩阵的宽度。
//同理,求出每一列的最小覆盖子串的长度,再求最小公倍数,就可以获得最小覆盖矩阵的高度了。
# include 
  
   
# include 
   
     # include 
    
      using namespace std; char a[10010][100]; int next[10010]; int n,m; int Getnext1(int r) { int i=0,j=-1; next[0]=-1; while(i<=m) { if(j==-1||a[r][i]==a[r][j]) i++,j++,next[i]=j; else j=next[j]; } return m-next[m]; } int Getnext2(int r) { int i=0,j=-1; next[0]=-1; while(i<=n) { if(j==-1||a[i][r]==a[j][r]) i++,j++,next[i]=j; else j=next[j]; } return n-next[n]; } int lcm(int a,int b)//最小公倍数模版 { int mul = a * b; int r = a % b; while(r) { a = b; b = r; r = a % b; } return mul / b; } int main() { int i,ans2,ans1; while(~scanf("%d%d",&n,&m)) { for(i=0; i
     
      m) { ans1=m; break; } } for(i=0; i
      
       n) { ans2=n; break; } } printf("%d\n",ans1*ans2); } return 0; } 
      
     
    
   
  

】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
分享到: 
上一篇poj3461 Oulipo (KMP模板题~) 前.. 下一篇URAL 1297 后缀数组:求最长回文..

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容: