← 返回题目列表

AtCoder · past202010_h

H. 方形切割

中文机器翻译题面 查看原题

分数: 6 点

警告

2020 年 11 月 8 日下午 6:00 之前请勿提及此问题。日本标准时间。如有违反,可要求赔偿。 考试结束后,您可以向其他人透露您的总分和成绩,但仅此而已(例如,您解决了哪些问题)。

问题陈述

给定一个正方形网格,其中 N 行和 M 列。每个方格上都写有一个数字;写在正方形上的数字 i从顶部开始的第行和 j左起第列是 s_{i,j}。 你的工作是选择一个整数 n 并剪出一个正方形网格 n 行和 n 列,其中所有方块都写有相同的数字。

的最大可能值是多少 n 最多什么时候可以选择 K 方块并更改这些方块上写的数字?

约束

  • 1 \leq N,M \leq 30
  • 0 \leq K \leq NM
  • 的长度 s_i (1 \leq i \leq N) is M.
  • s_{i,j} 是数字之一 0123456789.

输入

输入由标准输入按以下格式给出:

N M K
s_{1,1}\cdots s_{1,M}
\vdots
s_{N,1}\cdots s_{N,M}

输出

打印最大可能值 n 最多什么时候可以选择 K 方块并更改这些方块上写的数字。


示例输入 1

3 4 3
1123
1214
1810

示例输出 1

3
  • 让 (i,j) 表示位于 i从顶部开始的第行和 j左起第 列。
  • 如果更改写在 (1,3), (2,2),和 (3,2),将会有一个子网格 3 行和 3 所有方块都有的列 1 。

示例输入 2

8 6 40
846444
790187
264253
967004
578258
204367
681998
034243

示例输出 2

6