AT_cf_2015_relay_h 塗りつぶし

有一个高为 $H$、宽为 $W$ 的网格，左上角的格子坐标为 $(1, 1)$，右下角的格子坐标为 $(H, W)$。每个格子被涂上了 $1$ 到 $9$ 这 $9$ 种颜色中的一种。 你可以对这个网格进行若干次“填色”操作。一次填色操作是指：选择 $9$ 种颜色中的一种，将从 $(1, 1)$ 出发、所有与 $(1, 1)$ 连通且颜色相同的格子全部变为所选颜色。两个格子连通，指的是可以通过一系列边相连且颜色相同的格子互相到达。下面给出了填色操作的例子（图对应输入样例1）。  给定 $H \times W$ 的网格的初始状态，请求出使 $(1, 1)$ 和 $(H, W)$ 连通所需的最小填色操作次数。

输入从标准输入读入，格式如下： > $H$ $W$ > $c_{1,1}c_{1,2}\ldots c_{1,W}$ > $c_{2,1}c_{2,2}\ldots c_{2,W}$ > $\vdots$ > $c_{H,1}c_{H,2}\ldots c_{H,W}$ $H$、$W$（$2 \leq H, W \leq 500$）分别表示网格的高和宽。$c_{i,j}$（$1 \leq i \leq H, 1 \leq j \leq W, 1 \leq c_{i,j} \leq 9$）表示初始时第 $i$ 行第 $j$ 列的格子的颜色。

输出使 $(1, 1)$ 和 $(H, W)$ 连通所需的最小填色操作次数，输出一行，末尾换行。

### 样例解释1 按“颜色 $3$ → 颜色 $2$”的顺序填色后，$(1, 1)$ 和 $(3, 3)$ 就连通了。 ### 样例解释2 一开始 $(1, 1)$ 和 $(3, 3)$ 就已经连通。 由 ChatGPT 4.1 翻译