Picowso - новый гений!
Picowso рисует особым способом. Она начинает на пустом холсте размером N×N ячеек, представленном решёткой из N×N нолей, где ноль обозначает пустую ячейку холста. Затем она рисует N2 прямоугольников на холсте каждым из N2 цветов последовательно пронумерованных 1…N2. Например, она может начать рисовать прямоугольник цветом 2 и получится такой холст:
2 2 2 0
2 2 2 0
2 2 2 0
0 0 0 0
Затем она может нарисовать прямоугольник цветом 7:
2 2 2 0
2 7 7 7
2 7 7 7
0 0 0 0
А затем она может нарисовать маленький прямоугольник цветом 3:
2 2 3 0
2 7 3 7
2 7 7 7
0 0 0 0
Каждый прямоугольник имеет стороны, параллельные сторонам холста, и прямоугольник может быть таким большим как весь холст или таким маленьким как одна ячейка. Каждый цвет из 1…N2 используется ровно один раз, хотя более поздние цвета могут полностью перекрыть более ранние цвета.
По заданному финальному состоянию холста определите сколько из N2 цветов могли быть первым, использованным при рисовании.
ФОРМАТ ВВОДА:
Первая строка ввода содержит NN, размер холста (1≤N≤1000). Следующие N строк описывают финальную картину на холсте, каждая строка содержит NN целых чисел в интервале 0…N2. Гарантируется, что картина была нарисована способом описанным выше, рисованием прямоугольников различных цветов.
ФОРМАТ ВЫВОДА:
Выведите количество цветов, которые могли быть использованы первыми.
| Ввод |
Вывод |
|
4
2 2 3 0
2 7 3 7
2 7 7 7
0 0 0 0
|
14 |
В этом примере цвет 2 мог быть использован первым. Цвет 3 был использован после цвета 7, а цвет 7 был использован после цвета 2. Поскольку мы не видим других цветов, мы делаем вывод, что они также могли быть использованы первыми (а потом перекрашены).