codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

2069B.md (1980B)


      1 Source: https://codeforces.com/problemset/problem/2069/B
      2 
      3 B. Set of Strangers
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 You are given a table of $n$ rows and $m$ columns. Initially, the cell at the $i$-th row and the $j$-th column has color $a_{i, j}$.
     22 
     23 Let's say that two cells are strangers if they don't share a side. Strangers are allowed to touch with corners.
     24 
     25 Let's say that the set of cells is a set of strangers if all pairs of cells in the set are strangers. Sets with no more than one cell are sets of strangers by definition.
     26 
     27 In one step, you can choose any set of strangers such that all cells in it have the same color and paint all of them in some other color. You can choose the resulting color.
     28 
     29 What is the minimum number of steps you need to make the whole table the same color?
     30 
     31 Input
     32 
     33 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Next, $t$ cases follow.
     34 
     35 The first line of each test case contains two integers $n$ and $m$ ($1 \le n \le m \le 700$) — the number of rows and columns in the table.
     36 
     37 The next $n$ lines contain the colors of cells in the corresponding row $a_{i, 1}, \dots, a_{i, m}$ ($1 \le a_{i, j} \le nm$).
     38 
     39 It's guaranteed that the total sum of $nm$ doesn't exceed $5 \cdot 10^5$ over all test cases.
     40 
     41 Output
     42 
     43 For each test case, print one integer — the minimum number of steps to paint all cells of the table the same color.
     44 
     45 Example
     46 
     47 Input
     48 
     49 ```
     50 4
     51 
     52 1 1
     53 
     54 1
     55 
     56 3 3
     57 
     58 1 2 1
     59 
     60 2 3 2
     61 
     62 1 3 1
     63 
     64 1 6
     65 
     66 5 4 5 4 4 5
     67 
     68 3 4
     69 
     70 1 4 2 2
     71 
     72 1 4 3 5
     73 
     74 6 6 3 5
     75 ```
     76 
     77 Output
     78 
     79 ```
     80 0
     81 2
     82 1
     83 10
     84 ```
     85 
     86 Note
     87 
     88 In the first test case, the table is painted in one color from the start.
     89 
     90 In the second test case, you can, for example, choose all cells with color $1$ and paint them in $3$. Then choose all cells with color $2$ and also paint them in $3$.
     91 
     92 In the third test case, you can choose all cells with color $5$ and paint them in color $4$.