Сучасне мистецтво#10523

Сучасне мистецтво

1 секунда

128 мегабайтів

Середня

Світові мистецтвознавці лише нещодавно почали визнавати творчий геній великої художниці зі світу великої рогатої худоби — Піковсо (Picowso).

Піковсо малює доволі незвичним способом. Спочатку вона бере чисте полотно розміром $n \times n$ n \times n, представлене у вигляді сітки $n \times n$ n \times n, заповненої нулями, де нуль позначає порожню клітинку полотна. Потім вона малює на полотні до $9$ прямокутників, використовуючи один із $9$ кольорів, пронумерованих від $1$ до $9$ . Наприклад, спочатку вона може намалювати прямокутник кольором $2$ , отримавши такий проміжний варіант полотна:

Потім вона може намалювати прямокутник кольором $7$ :

Нарешті, вона може намалювати невеликий прямокутник кольором $3$ :

Сторони кожного прямокутника паралельні сторонам полотна. Прямокутник може бути розміром з усе полотно або складатися лише з однієї клітинки. Кожен колір від $1$ до $9$ використовується рівно один раз, хоча пізніші кольори можуть повністю закривати частини раніше намальованих кольорів.

За заданим кінцевим станом полотна визначте, скільки з кольорів, що залишилися видимими на фінальній картині, могли бути використані для малювання першого прямокутника.

Вхідні дані

У першому рядку міститься розмір полотна $n (1 \leq n \leq 10)$ n~(1 \le n \le 10). Наступні $n$ рядків описують кінцевий стан полотна. Кожен рядок містить $n$ цілих чисел, кожне з яких знаходиться в діапазоні від $0$ до $9$ . Гарантується, що вхідні дані могли бути отримані в результаті послідовного малювання прямокутників різними кольорами, як описано вище.

Вихідні дані

Виведіть кількість кольорів, які могли бути використані для малювання першого прямокутника серед усіх кольорів, що залишилися видимими на фінальній картині.

Приклади

У цьому прикладі лише колір $2$ міг бути використаний для малювання першого прямокутника. Очевидно, що колір $3$ мав бути нанесений після кольору $7$ , а колір $7$ — після кольору $2$ .

Приклад 1