程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> poj2185 Milking Grid (最小覆蓋矩陣)

poj2185 Milking Grid (最小覆蓋矩陣)

編輯:C++入門知識

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; im)
            {
                ans1=m;
                break;
            }
        }
        for(i=0; in)
            {
                ans2=n;
                break;
            }
        }
        printf("%d\n",ans1*ans2);
    }
    return 0;
}

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved