P10379 [GESP202403 Level 7] Tetris

Related multiple-choice and true/false problems: .

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. 

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 one line containing one integer, representing the answer.

| Subtask | Score | $n,m \leq$ | Special Rule | | :-: | :-: | :-: | :-: | | $1$ | $30$ | $20$ | Every Tetris block has a bounding box no larger than $5 \times 5$. | | $2$ | $30$ | $500$ | Every Tetris block is of type $1 \times x$ or $x \times 1$, where $x$ is any positive integer. | | $3$ | $40$ | $500$ | None. | Constraints: For all testdata, $1 \leq n, m \leq 500$, $1 \leq a_{i,j} \leq n \times m$. Translated by ChatGPT 5