المپدیا

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

ابزار کاربر

ابزار سایت


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

نگهبانان قصر

در دوران حکومت پادشاهی در اسلواکی، قصر پادشاه روی یک زمین مستطیل شکل $M\times N$ بنا شده بود. در واقع مستطیل از $M\times N$ مربع تشکیل شده بود که روی بعضی از مربع‌ها دیوار بنا شده بود، در بعضی از مربع‌های دیگر حفره‌ای با یک تمساح بود و بیقیه‌ی مربع‌ها آزاد بودند. با وجود تمساح‌ها شاه هنوز نگران بود و تصمیم گرفت تا روی مربع‌های آزاد تا آن‌جا که ممکن است نگهبان‌هایی قرار دهد که به محض دیدن هر جنبنده‌ای به سویش شلیک کنند. بنابراین لازم است نگهبان‌ها طوری قرار گیرند تا همدیگر را نبینند، چون به سوی هم شلیک خواهند کرد. هم‌چنین بدیهی است که در هر مربع آزاد حداکثر یک نگهبان قرار می‌گیرد. دو نگهبان در دو مربع آزاد هم‌دیگر را می‌بینند اگر و فقط اگر آن دو مربع در یک سطر و یا یک ستون باشند و بین آن‌ها دیواری نباشد. هر نگهبان فقط در چهار جهت عمود بر اضلاع مربع خود دید دارد (مثل رخ شطرنج).

مسئله

شما باید تعیین کنید شاه با رعایت مقررات فوق حداکثر چند نگهبان می‌تواند روی مربع‌های آزاد قرار دهد و یکی از ترکیب‌های ممکن محل قرار گرفتن نگهبان‌ها را نیز معین کنید.

ورودی

سطر اول فایل ورودی حاوی دو عدد $M$ و $N$ ( $1\leq M,N \leq 200$ ) است. سطر $i$ ام از هر یک از $M$ سطر بعدی حاوی $N$ عدد $a_{i,1}...a_{i,N}$ است که با یک فاصله‌ی خالی از هم جدا شده‌اند.

  • $a_{i,j}=0$ یعنی مربع $[i,j]$ آزاد است (نه دیوار است و نه حفره).
  • $a_{i,j}=1$ یعنی مربع $[i,j]$ یک حفره است.
  • $a_{i,j}=2$ یعنی مربع $[i,j]$ دیوار است.

خروجی

سطر اول خروجی باید حاوی عدد $K$ برابر حداکثر تعداد نگهبانی باشد که شاه می‌تواند روی مربع‌های آزاد قرار دهد. سطر $i$ ام از $K$ سطر بعدی باید حاوی دو عدد صحیح $r_i$ (سطر) و $c_i$ (ستون)، مختصات مربع محل قرار گرفتن نگهبان $i$ ام باشد که با یک فاصله‌ی خالی از هم جدا شده‌اند.

شکل قصر مربوط به مثال ورودی و خروجی زیر:

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

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

ابزار صفحه