問題一覧 > 通常問題

No.1668 Grayscale

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 56
作問者 : rianoriano / テスター : noiminoimi
7 ProblemId : 6312 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-08-31 01:27:00

問題文

あなたの手元に、1枚の白黒画像があります。
白黒といっても、 濃さの異なる灰色のグラデーションで表現されており、 $N$ 種類の色を含んでいます。 これらの色は「灰色の濃さ」と呼ばれる値で表され、この数値が同じであるときのみ、 $2$ つの灰色は同じ色であるとみなされます。
また、画像は縦 $H$ 行、横 $W$ 列のマスごとに色が塗られたもので、 上から $i$ 行目、左から $j$ 列目のマス $(i,j)$ の「灰色の濃さ」は $C_{ij}$ です。 あなたは、この画像を出来るだけ少ない色の画像に変換したいと考えています。
ただし、縦 $H$ 行、横 $W$ 列であり、上から $i$ 行目、左から $j$ 列目のマス $(i,j)$ の「灰色の濃さ」が $D_{ij}$ である画像で、次の条件を満たすようなものを生成することを、もとの画像の変換と呼びます。

■条件
1. 変換前の画像と変換後の画像で、任意の $2$ 色について「灰色の濃さ」の大小関係が逆転しない。
 厳密には、任意の $2$ マス $(i,j)$、$(k,l)$ に対して、 $C_{ij}≤C_{kl}$ ならば $D_{ij}≤D_{kl}$ である。
2. 変換の前後で「色の境目」は変化しない。
 すなわち、任意の辺を共有して隣接する $2$ マスについて、変換前に互いに「灰色の濃さ」が違うならば 変換後も「灰色の濃さ」が違う。

条件を満たす変換において、変換後の画像に現れる色の種類数の最小値を求めてください。

入力

$H$ $W$ $N$
$C_{11}$ $C_{12}$ ... $C_{1W}$
$C_{21}$ $C_{22}$ ... $C_{2W}$
... 
$C_{H1}$ $C_{H2}$ ... $C_{HW}$

$H$ は画像を構成するマスの行数、 $W$ は列数、 $N$ は変換前の画像に現れる色の種類数。
$C_{ij}$ は上から $i$ 行目、左から $j$ 列目のマス $(i,j)$ の「灰色の濃さ」を表す。

■制約
$1≤H,W≤1000$
$1≤N≤HW$
$1≤C_{ij}≤N$
$1≤k≤N$ を満たす任意の $k$ に対して、 $C_{ij}=k$ となるマス $(i,j)$ が存在する。
入力は全て整数である。

出力

題意の条件を満たす出力画像の色の種類数の最小値を出力してください。
最後に改行してください。

サンプル

サンプル1
入力
2 2 4
1 2
3 4
出力
3

灰色の濃さが $k$ である色を、色 $k$ と呼ぶことにします。
色 $2$ と色 $3$ を、どちらも $2$ にしてしまっても条件を満たすことが出来ます。
実際、色の境目である辺は色の境目のままであり、灰色の濃さの順序も逆転していないことが分かります。
これ以上色を減らそうとすると、例えば $1$ を $2$ に変換すると色の境目が境目でなくなってしまうなど、条件に反します。
従って、 $3$ 種類の色(説明の例では $1,2,4$ )が条件を満たす最小値ですので、 $3$ と答えてください。

サンプル2
入力
3 3 7
1 4 5
7 7 7
2 3 6
出力
4

色 $1$ と $2$ 、 $3$ と $4$ 、 $5$ と $6$ はそれぞれ同じ色にして構いません。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。