POJ--2158--------------Milking Grid(最小覆盖字符矩阵)---(开二维kmp)

时间:2022-11-12 15:30:36
Milking Grid
Time Limit: 3000MS   Memory Limit: 65536K
Total Submissions: 6169   Accepted: 2573

Description

Every morning when they are milked, the Farmer John's cows form a rectangular grid that is R (1 <= R <= 10,000) rows by C (1 <= C <= 75) columns. As we all know, Farmer John is quite the expert on cow behavior, and is currently writing a book about feeding behavior in cows. He notices that if each cow is labeled with an uppercase letter indicating its breed, the two-dimensional pattern formed by his cows during milking sometimes seems to be made from smaller repeating rectangular patterns.

Help FJ find the rectangular unit of smallest area that can be repetitively tiled to make up the entire milking grid. Note that the dimensions of the small rectangular unit do not necessarily need to divide evenly the dimensions of the entire milking grid, as indicated in the sample input below.

Input

* Line 1: Two space-separated integers: R and C

* Lines 2..R+1: The grid that the cows form, with an uppercase letter denoting each cow's breed. Each of the R input lines has C characters with no space or other intervening character.

Output

* Line 1: The area of the smallest unit from which the grid is formed 

Sample Input

2 5
ABABA
ABABA

Sample Output

2

Hint

The entire milking grid can be constructed from repetitions of the pattern 'AB'.

Source

 
 
这道题,题目不是很好懂,首先是  
aabcdeaa
acbdeead   
dakfdkkk      ---》求最小的子矩阵 其实很简单的呀,对一行求出最小的循环节点  对每一列求出最小的循环节点就行了max={max, RR-next[RR]} 
dasdsdd         max1 ={max1,CC-next[CC]};  然后相乘得到了他的面积:   max1*max ==ans;
 
 
代码:
 #include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
using namespace std;
const int row =;
const int cow =;
char str[row][cow];
int next[row][cow];
int RR,CC;
int main()
{
while(scanf("%d%d",&RR,&CC)!=EOF)
{
for(int i=;i<RR;i++)
scanf("%s",str[i]);
int i,j,k;
//先求出每一行的next
int max_row=-;
for(k=;k<RR;k++)
{
i=; j=-;
next[k][]=-;
while(i<CC)
{
if(j==-||str[k][i]==str[k][j])
{
i++;
j++;
next[k][i]=j;
}
else j=next[k][j];
}
if(max_row<(CC-next[k][CC]))
max_row=(CC-next[k][CC]);
}
int max_cow=-;
//求出所有列中的最小循环节
for(k=;k<CC;k++)
{
i=;
j=-;
next[][k]=-;
while(i<RR)
{
if(j==-||str[i][k]==str[j][k])
{
i++;
j++;
next[i][k]=j;
}
else
j=next[j][k];
}
if(max_cow<(RR-next[RR][k]))
max_cow=(RR-next[RR][k]);
}
printf("%d\n",max_row*max_cow);
}
return ;
}
 
 
 

POJ--2158--------------Milking Grid(最小覆盖字符矩阵)---(开二维kmp)的更多相关文章

  1. POJ 2185 Milking Grid KMP循环节周期

    题目来源:id=2185" target="_blank">POJ 2185 Milking Grid 题意:至少要多少大的子矩阵 能够覆盖全图 比如例子 能够用一 ...

  2. 依据矩阵的二维相关系数进行OCR识别

    我想通过简单的模板匹配来进行图像识别. 把预处理好的字符图片,分别与A到Z的样本图片进行模板匹配. 结果最大的表明相关性最大,就能够识别字符图片了. 在实际应用中.我用了openCV的matchTem ...

  3. 牛客练习赛1 矩阵 字符串二维hash&plus;二分

    题目 https://ac.nowcoder.com/acm/contest/2?&headNav=www#question 解析 我们对矩阵进行二维hash,所以每个子矩阵都有一个额hash ...

  4. 【c语言】二维数组中的查找,杨氏矩阵在一个二维数组中,每行都依照从左到右的递增的顺序排序,输入这种一个数组和一个数,推断数组中是否包括这个数

    // 二维数组中的查找,杨氏矩阵在一个二维数组中.每行都依照从左到右的递增的顺序排序. // 每列都依照从上到下递增的顺序排序.请完毕一个函数,输入这种一个数组和一个数.推断数组中是否包括这个数 #i ...

  5. 二维KMP - 求字符矩阵的最小覆盖矩阵 - poj 2185

    Milking Grid Problem's Link:http://poj.org/problem?id=2185 Mean: 给你一个n*m的字符矩阵,让你求这个字符矩阵的最小覆盖矩阵,输出这个最 ...

  6. POJ 2185 Milking Grid KMP(矩阵循环节)

                                                            Milking Grid Time Limit: 3000MS   Memory Lim ...

  7. poj 2185 Milking Grid

    Milking Grid http://poj.org/problem?id=2185 Time Limit: 3000MS   Memory Limit: 65536K       Descript ...

  8. POJ 2185 Milking Grid &lbrack;二维KMP next数组&rsqb;

    传送门 直接转田神的了: Milking Grid Time Limit: 3000MS   Memory Limit: 65536K Total Submissions: 6665   Accept ...

  9. 题解报告:poj 2185 Milking Grid(二维kmp)

    Description Every morning when they are milked, the Farmer John's cows form a rectangular grid that ...

随机推荐

  1. ADO&period;NET 读取Excel文件,并作数据源

    项目中需要用的功能,贴上代码了. 需要注意的地方:配置Web.config的时候要注意版本问题! //若是在Web.config中配置数据源,如下 <add key="ExcelCon ...

  2. mybatis实战教程&lpar;mybatis in action&rpar;之十:mybatis SqlSessionSupport 的使用&comma;构件DAO 层的应用

    前面的系列mybatis 文章,已经基本讲到了mybatis的操作,但都是基于mapper隐射操作的,在mybatis 3中这个mapper 接口貌似充当了以前在ibatis 2中的 DAO 层的作用 ...

  3. git 新建服务器的版本以及项目的用户

    一, git客户端账号生成 1. git的客户端的公钥生成 ssh-keygen -t rsa -C "test@gmail.com" mac机器会在 /Users/用户/.ssh ...

  4. 【干货分享】Node&period;js 中文资料导航

    这篇文章与大家分享一批高质量的的 Node.js 中文资料.Node.js 是一个基于 Chrome JavaScript 运行时建立的一个平台, 用来方便地搭建快速的, 易于扩展的网络应用 Node ...

  5. SVN强制注释

    1.目的 在使用SVN作为版本控制的时候,强制提交的人员写注释,这样能确保每次提交都有注释,方便查看 2.解决办法     2.1给工程加上属性          2.1.1在工程提交之后,通过客户端 ...

  6. SQLServer Agent执行&lbrack;分发清除&colon; distribution&rsqb; 无法删除快照文件

    由于之前创建的发布订阅造成严重的性能压力,症状表现为发布订阅表查询产生CMEMTHREAD  suspend等待,由于开发配置每隔十分钟会产生大量的SQLCOMMAND(create table,cr ...

  7. 剑指offer&lpar;1&rpar;

    题目: 在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序.请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数. ...

  8. &lt&semi;&lt&semi;操作,&amp&semi;0xff以及&vert;的巧妙运用(以POJ3523---The Morning after Halloween&lpar;UVa 1601&rpar;为例)

    <<表示左移,如a<<1表示将a的二进制左移一位,加一个0,&0xff表示取最后8个字节,如a&0xff表示取a表示的二进制中最后8个数字组成一个新的二进制数, ...

  9. css实现带箭头的流程条

    直接上效果图: <ul class="navs"> <li>1</li> <li>2</li> <li>3& ...

  10. python下的Box2d物理引擎的配置

    /******************************* I come back! 由于已经大四了,正在找工作 导致了至今以来第二长的时间内没有更新博客.向大家表示道歉 *********** ...