POJ2185-Milking Grid(KMP,next数组的应用)
2024-09-07 18:54:24
Milking Grid
Time Limit: 3000MS | Memory Limit: 65536K | |
Total Submissions: 6317 | Accepted: 2648 |
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.
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.
* 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
题意:r*c的字符串,问用最小的面积的字符串去覆盖它。求最小的面积
思路:能够分行分列考虑,easy想到当仅仅考虑行的时候,仅仅要把每一行看成一个字符,就能够求出关于行的next数组,然后求出最短的循环串 r-next[r] ,列也是如此,所以终于答案就是 (c-P[c])*(r-F[r]) P,F分别为各自的next数组。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn = 10000+10;
const int maxm = 80;
char mat[maxn][maxm];
char revmat[maxm][maxn];
int r,c;
int P[maxn],F[maxn];
int gcd(int a,int b) {
if(b==0) return a;
else return gcd(b,a%b);
}
void getP() {
P[1] = P[0] = 0;
for(int i = 1; i < r; i++) {
int j = P[i];
while(j && strcmp(mat[i],mat[j])) j = P[j];
if(strcmp(mat[i],mat[j])==0) P[i+1] = j+1;
else P[i+1] = 0;
}
}
void getF() {
F[1] = F[0] = 0;
for(int i = 1; i < c; i++) {
int j = F[i];
while(j && strcmp(revmat[i],revmat[j])) j = F[j];
if(strcmp(revmat[i],revmat[j])==0) F[i+1] = j+1;
else F[i+1] = 0;
}
}
void getRev() {
for(int i = 0; i < c; i++) {
for(int j = 0; j < r; j++) {
revmat[i][j] = mat[j][i];
}
}
}
void solve() {
int L = r-P[r],R = c - F[c];
printf("%d\n",L*R);
}
int main(){ while(~scanf("%d%d",&r,&c)){
for(int i = 0; i < r; i++) scanf("%s",mat[i]);
getP();
getRev();
getF();
solve();
}
return 0;
}
最新文章
- Java实现约瑟夫环
- Ubuntu 15.1 unity在顶部面板显示系统CPU/内存/网络速度
- oracle 存储过程中调用存储过程
- c#上传文件(一)使用 .net 控件上传文件
- Python:操作文件
- 4. 星际争霸之php设计模式--工厂方法模式
- web前端开发分享-css,js入门篇(转)
- UVALive 7464	Robots (贪心)
- apache开源项目-- NiFi
- Oracle 数据库(oracle Database)Select 多表关联查询方式
- 开源的连接池技术DBCP和C3P0
- @property的特性
- php get_ini 和 get_cfg_var 的区别
- C#调用SCL2008 动态库SCL_API_cdecl.dll or SCL_API_Stdcall.dll,提示找不到指定模块
- linux shell变量$#,$@,$0,$1,$2的含义解释
- CA认证的原理和流程及https原理
- 阿里的maven镜像仓库,eclipse中使用maven下载jar包的时候提升速度
- 【Java基础】12、java中方法的参数传递机制
- flask 基本操作 模板语言 session
- LintCode——合并排序数组II