Misha and Paintings

题意翻译

### 题目描述 给你一个 $n\times n$ 的矩阵 $a$，你可以对 $a$ 进行任意次操作，操作的具体步骤如下： + 选择矩阵 $a$ 的一个正方形子矩阵； + 选择一个正整数数 $x$，其中 $1\leq x\leq n^2$； + 将子矩阵内的所有元素修改为 $x$。 你需要求出使矩阵 $a$ 恰好包含 $k$ 个不同元素所需的最小操作次数。 最小操作次数可以为 $0$。 ### 输入格式 第一行两个整数 $n,k$，表示矩阵大小和矩阵最终恰好包含的不同元素个数。 接下来 $n$ 行，每行 $n$ 个正整数，第 $i+1$ 行第 $j$ 个数表示矩阵 $a$ 的第 $i$ 行第 $j$ 列的元素。 ### 输出格式 输出一行一个非负整数，表示最小修改次数。 ### 数据范围 $1\leq n\leq 500,1\leq a_{i,j},k\leq n^2$。

题目描述

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: 1. 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 $ ), 2. choose an integer $ k $ , where $ 1 \leq k \leq n^2 $ , 3. 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

**米莎和画作**

**题意翻译**

### 题目描述

给定一个 $n \times n$ 的矩阵 $a$，你可以对 $a$ 进行任意次数的操作，操作的具体步骤如下：

+ 选择矩阵 $a$ 的一个正方形子矩阵；
+ 选择一个正整数 $x$，其中 $1 \leq x \leq n^2$；
+ 将子矩阵内的所有元素修改为 $x$。

你需要求出使矩阵 $a$ 恰好包含 $k$ 个不同元素所需的最小操作次数。

最小操作次数可以为 $0$。

### 输入格式

第一行两个整数 $n,k$，表示矩阵大小和矩阵最终恰好包含的不同元素个数。

接下来 $n$ 行，每行 $n$ 个正整数，第 $i+1$ 行第 $j$ 个数表示矩阵 $a$ 的第 $i$ 行第 $j$ 列的元素。

### 输出格式

输出一行一个非负整数，表示最小修改次数。

### 数据范围

$1 \leq n \leq 500, 1 \leq a_{i,j},k \leq n^2$。

**题目描述**

米莎有一个 $n \times n$ 的矩阵，其中第 $i$ 行第 $j$ 列的数字是 $a_{i, j}$。米莎想要修改矩阵以使其恰好包含 $k$ 个不同的整数。为了达到这个目标，米莎可以执行以下操作零次或多次：

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$。

请找出米莎达到目标所需的最小操作次数。

**输入输出格式**

**输入格式**

第一行输入包含两个整数 $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
```**米莎和画作** **题意翻译** ### 题目描述 给定一个 $n \times n$ 的矩阵 $a$，你可以对 $a$ 进行任意次数的操作，操作的具体步骤如下： + 选择矩阵 $a$ 的一个正方形子矩阵； + 选择一个正整数 $x$，其中 $1 \leq x \leq n^2$； + 将子矩阵内的所有元素修改为 $x$。 你需要求出使矩阵 $a$ 恰好包含 $k$ 个不同元素所需的最小操作次数。 最小操作次数可以为 $0$。 ### 输入格式 第一行两个整数 $n,k$，表示矩阵大小和矩阵最终恰好包含的不同元素个数。 接下来 $n$ 行，每行 $n$ 个正整数，第 $i+1$ 行第 $j$ 个数表示矩阵 $a$ 的第 $i$ 行第 $j$ 列的元素。 ### 输出格式 输出一行一个非负整数，表示最小修改次数。 ### 数据范围 $1 \leq n \leq 500, 1 \leq a_{i,j},k \leq n^2$。 **题目描述** 米莎有一个 $n \times n$ 的矩阵，其中第 $i$ 行第 $j$ 列的数字是 $a_{i, j}$。米莎想要修改矩阵以使其恰好包含 $k$ 个不同的整数。为了达到这个目标，米莎可以执行以下操作零次或多次： 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$。 请找出米莎达到目标所需的最小操作次数。 **输入输出格式** **输入格式** 第一行输入包含两个整数 $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 ```