+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۵۱۲ مگابایت + روز ۱ دوره ۳۱ ---------- دان دریایی کاراییب در زندانی قرار دارند که به شکل جدولی $n \times n$است. از آنجایی که جک در جوانی المپیاد کامپیوتری بوده کامپیوتر مرکزی زندان را هک کرده و متوجه شده است که اتاق آن ها در خانه $(1, 1)$ جدول و در خروجی زندان در خانه $(n, n)$ قرار دارد. هر کدام از خانه‌های جدول یک اتاق است که چهار در دارد که هر کدام روی یکی از ضلع های مربع هستند. جک بعد از هک کردن کامپیوتر مرکزی متوجه شد که بعضی از خانه‌های جدول مین گذاری شده‌اند. طبعا هیچ‌کس دوست ندارد از روی مین رد بشود. حالا مسئله این است که جک می‌خواهد گروهش را به بیشترین تعداد دسته ممکن افراز کند و هر گروه از یک مسیر جدا برود. به این معنی که جک نیاز دارد بیشترین تعداد مسیر فرار ممکن را بداند به طوریکه هیچ اتاقی در دو مسیر دیده نشود (به جز اتاق شروع و پایان). و البته واضح است که این بیشترین تعداد مسیر ممکن حداکثر ۲ هست. حالا قرار است جک به شما مختصات مین ها را یکی یکی بدهد و بعد از هر کوئری شما بیشترین تعداد مسیر ممکن را بگویید! # پیاده‌سازی جک طی تحقیقاتش فهمید که مشتلی مسئول زندان است. همه ما می‌دانیم که جک و مشتلی از زمان المپیادشان تا الان دشمنان خونین همدیگر هستند. بنابراین مشتلی برای اینکه اطمینان حاصل کند جک از زندان فرار نمی‌کند به شایان دستور داد که هرگونه ارتباط از داخل زندان به خارج را ببندد و شایان نیز چنین کرد ولی از آنجایی که قبلا از جک رشوه گرفته بود ارتباط از خارج زندان به داخل را نبست! بنابراین جک نمی‌تواند مختصات مین‌ها را برای شما بفرستد پس از شما می‌خواهد تابعی پیاده سازی کنید که جواب مسئله را بدهد. یعنی در این سوال شما اجازه خواندن از ورودی یا نوشتن در خروجی را ندارید. شما باید توابع زیر را پیاده سازی کنید و جک از آنها استفاده می‌کند. همچنین برنامه شما نباید تابع main داشته باشد. در صورت هرگونه تلاش برای خواندن از ورودی یا نوشتن در خروجی یا استفاده از تابع exit نمره شما صفر می‌شود. ```cpp void init(int n, int q) ``` شما باید این تابع را پیاده‌سازی کنید. در ابتدای فرایند این تابع تنها یک بار صدا زده می‌شود و مقادیر $n, q$ را به شما می‌دهد. + n: اندازه طول و عرض زندان + q: bomb تعداد بار‌های فراخوانی تابع ```cpp int bomb(int x, int y) ``` شما باید این تابع را پیاده‌سازی کنید. جک با صدا زدن این تابع به شما مختصات یک مین جدید را می‌دهد. خروجی این تابع باید بیشترین تعداد مسیر فرار ممکن با اطلاعات فعلی باشد. $$2 \leq n \leq 3000$$ $$1 \leq q \leq min(2\times10^5, n^2-2)$$ $$1 \leq x,y \leq n$$ تضمین می‌شود که $x,y$ ها غیر‌تکراری هستند. همچنین خانه شروع و پایان هیچوقت مین‌گذاری نمی‌شوند. # ارزیاب نمونه دو تابع خواسته شده را در فایل TheGreatEscape.cpp پیاده‌سازی کنید. لازم نیست جواب شما تنها شامل این دو تابع باشد بلکه بسته به نیاز خود می‌توانید توابع دیگر نیز تعریف کنید. ولی برنامه شما نباید تابع main داشته باشد. برای کامپایل کردن برنامه باید compile\_cpp.sh را اجرا کنید. حاصل کامپایل فایل اجرایی TheGreatEscape خواهد بود که همان ارزیاب نمونه است. سپس فایل اجرایی TheGreatEscape را که توسط compile\_cpp.sh تولید شده است،‌ اجرا کنید. ارزیاب نمونه در خط اول اعداد $n,q$ را به ترتیب می‌خواند. سپس $q$ خط دیگر می‌خواند که در هر کدام ابتدا عدد $x$ و سپس $y$ آمده است. هر خط نشان دهنده یک کوئری انفجار مین است. # زیرمسئله‌ها | زیرمسئله | نمره | محدودیت |:------------------:|:----------:|:------------------:| | ۱ | ۲ | $n \le 4$ | | ۲ | ۵ | $n \le 10$ | | ۳ | ۱۳ | $n \le 100$ | | ۴ | ۳۱ | اولین کوئری $x=1,y=2$ است | | ۵ | ۷ | ناحیه مین‌گذاری شده همبند است | | ۶ | ۱۸ | ناحیه مین‌گذاری شده حداکثر $10$ مولفه همبندی دارد. | | ۷ | ۲۴ | بدون محدودیت اضافی | # مثال ## ورودی نمونه ۱ ``` 5 7 4 1 3 2 2 3 3 3 3 4 1 4 4 5 ``` ## خروجی نمونه ۱ ``` 2211100 ``` ## ورودی نمونه ۲ ``` 6 6 3 1 2 3 3 3 4 3 5 3 5 2 ``` ## خروجی نمونه ۲ ``` 222222 ``` ## ورودی نمونه ۳ ``` 9 18 6 6 3 4 3 1 6 8 3 2 6 4 3 5 6 7 3 3 3 7 6 5 6 3 6 9 3 6 2 5 4 1 7 6 1 5 ``` ## خروجی نمونه ۳ ``` 222222222222221110 ```

حل سؤال در بانک سؤالات