Background

Related multiple-choice and true/false problems: https://ti.luogu.com.cn/problemset/1147.

Problem Description

Student Xiao Yang filled a grid of size $n \times m$ using different kinds of Tetris blocks.

The grid consists of $n \times m$ colored cells. Xiao Yang now gives you this grid and asks you to compute how many different kinds of Tetris blocks appear in the grid.
If two cells of the same color are 4-connected (i.e., adjacent in one of the four directions: up, down, left, right), then the two cells are said to be directly connected. If two cells of the same color are both directly or indirectly connected to another cell of the same color, then the two cells are said to be indirectly connected. A Tetris block consists of one cell and all same-colored cells that are directly or indirectly connected to it. Two Tetris blocks are defined to be of the same kind if and only if one block can be translated to overlap exactly with the other; if two Tetris blocks have different colors, they are still considered the same kind.

For example, in the following figure, block $1$ and block $2$ are the same kind of Tetris block, while block $1$ and block $3$ are not the same kind of Tetris block.

Input Format

The first line contains two positive integers $n$ and $m$, representing the size of the grid.
In the next $n$ lines, the $i$-th line contains $m$ positive integers $a_{i1}, a_{i2}, \dots a_{im}$, representing the colors of the $m$ cells in that row.

Output Format

Output one line containing one integer, representing the answer.

5 6
1 2 3 4 4 5
1 2 3 3 4 5
1 2 2 3 4 5
1 6 6 7 7 8
6 6 7 7 8 8

7

Hint

Constraints: For all testdata, $1 \leq n, m \leq 500$, $1 \leq a_{i,j} \leq n \times m$.

Translated by ChatGPT 5