CF1720E.Misha and Paintings

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

Misha has a square $n \times n$ matrix, where the number in row $i$ and column $j$ is equal to $a_{i, j}$ . Misha wants to modify the matrix to contain exactly $k$ distinct integers. To achieve this goal, Misha can perform the following operation zero or more times:

choose any square submatrix of the matrix (you choose $(x_1,y_1)$ , $(x_2,y_2)$ , such that $x_1 \leq x_2$ , $y_1 \leq y_2$ , $x_2 - x_1 = y_2 - y_1$ , then submatrix is a set of cells with coordinates $(x, y)$ , such that $x_1 \leq x \leq x_2$ , $y_1 \leq y \leq y_2$ ),
choose an integer $k$ , where $1 \leq k \leq n^2$ ,
replace all integers in the submatrix with $k$ .

Please find the minimum number of operations that Misha needs to achieve his goal.

输入格式

The first input line contains two integers $n$ and $k$ ( $1 \leq n \leq 500, 1 \leq k \leq n^2$ ) — the size of the matrix and the desired amount of distinct elements in the matrix.

Then $n$ lines follows. The $i$ -th of them contains $n$ integers $a_{i, 1}, a_{i, 2}, \ldots, a_{i, n}$ ( $1 \leq a_{i,j} \leq n^2$ ) — the elements of the $i$ -th row of the matrix.

输出格式

Output one integer — the minimum number of operations required.

输入输出样例

输入#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
```

说明/提示

In the first test case the answer is $1$ , because one can change the value in the bottom right corner of the matrix to $1$ . The resulting matrix can be found below:

111112341In the second test case the answer is $2$ . First, one can change the entire matrix to contain only $1$ s, and the change the value of any single cell to $2$ . One of the possible resulting matrices is displayed below:

111111112

首页