المپدیا

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

ابزار کاربر

ابزار سایت


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

قبیله‌ها

یک جنگل استوایی یک مستطیل بزرگ است که $m$ کیلومتر عرض و $n$ کیلومتر طول دارد و از $m\times n$ خانه‌ی یک کیلومتر مربعی تشکیل شده است. تعدادی از این خانه‌ها به برکه‌های غیر قابل عبور تبدیل شده‌اند. در این جنگل تعدادی انسان‌نما وجود دارند که می‌توانند از هر خانه‌ی غیر برکه به چهار خانه‌ی مجاور آن (در صورت برکه نبودن) بروند می‌دانیم که هر چند انسانی که بتوانند با طی مسیری در جدول به هم برسند بالاخره تشکیل یک قبیله را می‌دهند. می‌خواهیم قبیله‌هایی که در نهایت تشکیل خواهند شد را بیابیم.

ورودی

در سطر اول فایل ورودی طول و عرض جدول آمده‌اند ($n$ و $m$) و در $n$ سطر بعدی در هر سطر $m$ عدد آمده‌اند. اگر عدد $j$ ام از سطر $i$ ام ۰ باشد خانه‌ی $(i,j)$ جدول برکه است، اگر ۱- باشد این خانه‌ی جدول برکه نیست و اگر عدد مثبت $x$ باشد انسان‌نمای $x$ ام در این‌جا ایستاده است. (مقدار $n$ حداکثر $10^6$ و مقدار $m$ حداکثر ۱۰۰ است و می‌توانید فرض کنید تعداد انسان‌نماها حداکثر $10^5$ بوده و شماره‌های آن‌ها از ۱ تا تعداد آن‌هاست.)

خروجی

در سطر اول تعداد قبیله‌ها و در سطرهای بعدی در هر سطر شماره‌ی انسان‌نماهای عضو آن قبیله را بنویسید. ترتیب نوشتن انسان‌نماها در قبایل و ترتیب نوشتن قبایل اهمیتی ندارد.

محدودیت‌ها

  • محدودیت زمان: ۲۵ ثانیه
  • محدودیت حافظه: ۱۰ مگابایت

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

ورودي نمونه خروجي نمونه
5 3
-1 2 -1
1 -1 0
-1 0 -1
0 -1 3
5 4 0
3
1
2
3 4 5

ابزار صفحه