| 题目名称 | 3593. [POJ 2185]奶牛矩阵 |
|---|---|
| 输入输出 | mgrid.in/out |
| 难度等级 | ★★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 13 |
| 题目来源 |
 syzhaoss
于2021-05-25加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：0， 提交：7， 通过率：0% | ||||
 ┭┮﹏┭┮ |
92 | 0.008 s | 1.57 MiB | C++ |
|
┭┮﹏┭┮ |
62 | 0.056 s | 1.57 MiB | C++ |
|
┭┮﹏┭┮ |
62 | 0.071 s | 1.57 MiB | C++ |
|
┭┮﹏┭┮ |
54 | 0.000 s | 0.00 MiB | C++ |
|
┭┮﹏┭┮ |
46 | 0.059 s | 1.57 MiB | C++ |
|
┭┮﹏┭┮ |
46 | 0.069 s | 1.57 MiB | C++ |
|
┭┮﹏┭┮ |
0 | 0.006 s | 6.82 MiB | C++ |
| 关于 奶牛矩阵 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
cuo(多重kmp吗？)
| ||||
|
耗子徐你还在啊
 此账号已注销
2023-10-07 17:17
1楼
| ||||
【题目描述】
每天早上，农夫约翰的奶牛们被挤奶的时候，都会站成一个 R 行 C 列的方阵。
现在在每个奶牛的身上标注表示其品种的大写字母，则所有奶牛共同构成了一个 R 行 C 列的字符矩阵。
现在给定由所有奶牛构成的矩阵，求它的最小覆盖子矩阵的面积是多少。
如果一个子矩阵无限复制扩张之后得到的矩阵能包含原来的矩阵，则称该子矩阵为覆盖子矩阵。
【输入格式】
第 1 行：输入两个用空格隔开的整数，R 和 C。
第 2..R+1 行：描绘由奶牛构成的 R 行 C 列的矩阵，每行 C 个字符，字符之间没有空格。
【输出格式】
输出最小覆盖子矩阵的面积。（每个字符的面积为 1）
【样例输入】
2 5 ABABA ABABA
【样例输出】
2
【样例说明】
样例中给出的矩阵的最小覆盖子矩阵为 AB，面积为 2。
【数据规模与约定】
$1\leq R\leq 10000,1\leq C\leq 75$。
【来源】
USACO 2003 Fall,CH1808