Код Ланцюга
У чорно-білому (двохрівневому) зображенні, колекції з'єднаних чорних пікселів можуть бути визначені як передній план або об'єкти, тоді як білі можуть вважатися фоном. Кожен набір з'єднаних чорних пікселів можна повністю описати, перерахувавши позиції пікселів на його межі у проти годинникової стрілки, починаючи з деякої довільної точки на межі. Цей список пікселів може бути представлений як послідовність напрямків до наступного пікселя в списку. Такий список напрямків називається ланцюговим кодом об'єкта і точно описує форму об'єкта, будучи незалежним від його позиції.
Існує 8 можливих напрямків від одного пікселя до сусіднього, і хоча призначення цих чисел є довільним, рисунок 1 показує стандартну конвенцію. Напрямок 0 означає "праворуч", 2 "вгору", а 1 знаходиться під кутом 45 градусів, розділяючи 0 і 2, і так далі.
Два чорні пікселі вважаються сусідніми, якщо квадрат відстані між ними менший або дорівнює 2. Це базується на стандартній графічній системі координат, де піксель знаходиться в кожній цілій координаті. Два пікселі з'єднані, якщо між ними можна простежити безперервний шлях сусідніх пікселів. З'єднана область - це набір чорних пікселів, у якому всі елементи з'єднані один з одним. Піксель на межі з'єднаної області (надалі просто області) - це піксель у межах області, який має принаймні одного сусіда (у чотирьох компасних напрямках), який не є чорним. Для цієї задачі ви можете припустити, що в області немає "дір", так що є лише одна межа області.
Ланцюговий код області може починатися з будь-якого пікселя на межі. Він продовжується шляхом знаходження наступного сусіднього пікселя на межі у проти годинникової стрілки, збереження напрямку (0-7) у вихідному буфері, а потім продовження процесу з нового пікселя. Коли ми знову досягаємо початкового пікселя, ланцюговий код завершено. Вихідний буфер містить набір значень напрямків, які складають сам ланцюговий код, і з яких можна відновити початковий набір пікселів, починаючи з будь-якої позиції пікселя на зображенні.
Як приклад, ланцюговий код для області на рисунку 2 - це 446567001232. Ланцюговий код однозначно описує форму області, хоча її позиція повністю невідома. Показники, пов'язані з формою, такі як периметр і площа (кількість пікселів в області), можуть бути визначені безпосередньо з опису ланцюгового коду. Ви повинні написати програму, яка обчислює площу з'єднаної області, маючи лише ланцюговий код.
Вхідні дані
Вхідні дані будуть колекцією рядків ланцюгового коду, по одному на рядок. Кожен ланцюговий код містить не більше 1000000 символів. Ви можете припустити, що кожен ланцюговий код описує дійсну область і не описує межу, яка перетинає сама себе.
Вихідні дані
Для кожного ланцюгового коду у вхідних даних, вихідними даними буде площа області (тобто кількість пікселів, що належать до неї), кожна надрукована на своєму рядку.