المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی انتخاب تیم:دوره ی ۱۴:سوال ۱۵

مولفه‌های تصویر

تصاویر سیاه و سفید معمولا به صورت توری مستطیلی ذخیره می‌شوند. یک چند خطی بین نقاط $P$ و $Q$ دنباله‌ای از نقاط سیاه به شکل $p_1,p_2,...,p_k$ می‌باشد که $p_1=P$ و $p_k=Q$ و هم‌چنین $p_i$ و $p_{i+1}$ ها به صورت افقی یا عمودی همسایه هستند. یک چندخطی را بسته گوییم اگر تنها نقاط تکراری آن نقاط ابتدا و انتهایش باشند. یک مجموعه از نقاط سیاه را همبند می‌گوییم اگر بین هر دو نقطه‌اش یک چندخطی از نقاط سیاه موجود باشد. یک مولفه، مجموعه‌ی همبند بیشینه‌ای از نقاط سیاه است. یک مولفه می‌تواند سوراخی را احاطه کند. یک سوراخ مجموعه‌ای از نقاط سیاه است که داخل یک چندخطی بسته‌ی سیاه قرار دارند. اگر یک مولفه سوراخی را احاطه نکند، آن را فشرده گوییم. شما باید برنامه‌ای بنویسید که تعداد کل مولفه‌ها و مولفه‌های فشرده‌ی یک تصویر کد شده را حساب کند. هر سطر به صورت یک رشته‌ی $b_1,w_1,b_2,,w_2,...,b_k,w_k$ کد می‌شود که $b_i$ ها تعداد نقاط سیاه متوالی و $w_i$ ها هم تعداد نقاط سفید متوالی را مشخص می‌کند.

در شکل بالا دقت کنید که نقطه‌ی سفیدی که با $x$ نشان داده شده، داخل چندخطی بسته‌ی رسم شده نیست.

ورودی

اولین سطر دو عدد صحیح مثبت $n$ و $m$ را دارد؛ به طوری که $2\leq n \leq 10^4$ تعداد سطرها را نشان می‌دهد و $2\leq m \leq 1000$ تعداد ستون‌ها را معین می‌سازد. $n$ سطر بعدی تصویر کدشده را نشان می‌دهد و در انتهای هر خط ۱- نوشته شده است.

خروجی

خروجی شامل دو سطر است و در هر سطر یک عدد صحیح نوشته شده. اولی تعداد مولفه‌های شکل و دیگری تعداد مولفه‌های فشرده را نشان می‌دهد.

ورودي و خروجي نمونه

ورودي نمونه خروجي نمونه
10 20
4 7 4 4 1 0 -1
0 4 1 4 1 4 1 1 1 3 -1
1 3 4 6 2 4 -1
0 7 9 4 -1
0 1 4 9 1 1 4 0 -1
0 1 1 3 1 8 1 5 -1
0 1 1 1 1 1 1 8 1 1 3 1 -1
0 1 1 3 1 1 3 1 2 1 1 1 3 1 -1
0 1 5 1 1 6 1 1 3 1 -1
0 7 3 4 1 1 3 1 -1
5
2

ابزار صفحه