No.509 塗りつぶしツール

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 116
作問者 : はむこはむこ / テスター : ixmelixmel

6 ProblemId : 1337 / 出題時の順位表

問題文

はむこさんはペイントというお絵かきソフトで、白背景に黒数字の画像を作りました。
しかし、本当に必要だったのは黒背景に白数字の画像だったことに気づきました。

はむこさんは、画像を一から作り直すのが面倒だったので、「塗りつぶしツール」のみを使ってこれを行おうとしています。
塗りつぶしツールは、隣り合った色が同じである限り、全てを指定した色に変更するツールです。

画像の変更に、最低何回塗りつぶしツールを使う必要があるでしょうか?

一回の画像変更で使える色は、「白」「黒」「白・黒以外の一色」に限定するものとします。

入力

n

$0 \leq n \leq 10^9$, $n$は整数
それぞれの数字の形は、以下です。

出力

題意の最小回数を1行で出力してください。 最後に改行してください。

サンプル

サンプル1
入力
6
出力
4

もともとの画像は以下のようになっている。

(1) 6の文字自体を赤に塗りつぶす

(2) 背景を黒に塗りつぶす

(3) 6の穴を黒に塗りつぶす

(4) 6の文字自体を白に塗りつぶす

サンプル2
入力
1
出力
3

もともとの画像は以下のようになっている。

(1) 1の文字自体を青に塗りつぶす

(2) 背景を黒に塗りつぶす

(3) 1の文字自体を白に塗りつぶす

サンプル3
入力
1046928
出力
21

提出ページヘ