← 返回题目列表

Codeforces · 1720/E

E. 米莎和绘画

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

Misha 有一个 $$$n \times n$$$ 方阵,其中行 $$$i$$$ 和列 $$$j$$$ 中的数字等于 $$$a_{i, j}$$$。 Misha 想要修改矩阵以恰好包含 $$$k$$$ 个不同的整数。为了实现这一目标,Misha 可以执行以下操作零次或多次:

1. 选择矩阵的任意方子矩阵(选择 $$$(x_1,y_1)$$$, $$$(x_2,y_2)$$$,使得 $$$x_1 \leq x_2$$$, $$$y_1 \leq y_2$$$, $$$x_2 - x_1 = y_2 - y_1$$$,那么子矩阵是一组坐标为 $$$(x, y)$$$ 的单元格,使得 $$$x_1 \leq x \leq x_2$$$, $$$y_1 \leq y \leq y_2$$$),
2. 选择一个整数 $$$k$$$,其中 $$$1 \leq k \leq n^2$$$,
3. 将子矩阵中的所有整数替换为$$$k$$$。

请找出 Misha 实现目标所需的最少操作次数。

输入

第一个输入行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \leq n \leq 500, 1 \leq k \leq n^2$$$) — 矩阵的大小以及矩阵中不同元素的所需数量。

然后是 $$$n$$$ 行。其中第 $$$i$$$ 包含 $$$n$$$ 整数 $$$a_{i, 1}, a_{i, 2}, \ldots, a_{i, n}$$$ ($$$1 \leq a_{i,j} \leq n^2$$$) — 矩阵第 $$$i$$$ 行的元素。

输出

输出一个整数——所需的最少运算次数。

示例

输入 #1

3 4
1 1 1
1 1 2
3 4 5

输出 #1

1

输入 #2

3 2
2 1 3
2 1 1
3 1 2

输出 #2

2

输入 #3

3 3
1 1 1
1 1 2
2 2 2

输出 #3

1

输入#4

3 2
1 1 1
1 2 1
2 2 2

输出#4

0

注意

在第一个测试用例中,答案是 $$$1$$$,因为可以将矩阵右下角的值更改为 $$$1$$$。生成的矩阵如下所示:

111112341

在第二个测试用例中,答案是 $$$2$$$。首先,可以将整个矩阵更改为仅包含 $$$1$$$,并将任何单个单元格的值更改为 $$$2$$$。可能的结果矩阵之一如下所示:

111111112