+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- امین و مهدی دارند یک بازی معروف را بازی می‌کنند. این بازی به این شکل است: یک شبکه $n \times n$ از نقاط روی یک برگ کاغذ کشیده می‌شود. سپس بازیکنان به نوبت دو نقطه مجاور را به هم متصل می‌کنند (از نظر افقی یا عمودی). در هر «حرکت» یک بازیکن می‌تواند یک خط بکشد که دو نقطه را به هم وصل کند. هر زمان که یک بازیکن موفق به بستن یک مربع $1 \times 1$ از نقاط می‌شود (یعنی، به واقعیت ۴ نقطه را با دقیقاً ۴ خط وصل می‌کند)، آن بازیکن مربع را «برنده» می‌شود و اولین حرف از نامش (`A` یا `B`) را در فضای خالی درون مربع می‌نویسد. در شرایط عادی، هر بازیکن تلاش می‌کند تا از این مربع‌ها به حد امکان استفاده کند (این بازی باعث خراب شدن دوستی‌های زیادی شده است). امین و مهدی دارند این بازی را بازی می‌کنند اما هر دو خجالتی‌اند و نمی‌خواهند که امتیازی را در برابر هم بگیرند. علاوه بر این، آن‌ها نمی‌خواهند دوستی‌شان را به خاطر یک بازی خراب کنند. امین و مهدی **سعی نمی‌کنند برنده شوند**، آن‌ها فقط می‌خواهند ادامه دادن بازی را و دوستی‌شان **تا زمان امکان‌پذیر** برای ادامه بازی لذت ببرند. با توجه به تنظیمات بازی که تا الان به آن رسیده‌اند، به آن‌ها کمک کنید تا **تعداد حرکاتی که می‌توانند انجام دهند بدون ایجاد هیچ مربع $1 \times 1$ از نقاط** را محاسبه کنند. # ورودی در سطر اول ورودی، عدد صحیح $n$، اندازه شبکه، آمده است. $$2 \leq n \leq 80$$ سپس یک نسخه از کاراکترهای نقشه بازی آمده است. نقشه به این شکل است که شما یک ماتریس $(2n-1) \times (2n-1)$ از کاراکترها را به ترتیب ردیف-به-ردیف دریافت می‌کنید. هر سلول می‌تواند از چهار نوع ممکن باشد ($1 \leq i, j \leq n$): + سلول در $(2i - 1, 2j - 1)$ علامت `*` دارد که نقطه $(i, j)$ را نشان می‌دهد. + سلول در $(2i, 2j)$ علامت `.` دارد که فضای خالی را نشان می‌دهد. + سلول در $(2i, 2j - 1)$ علامت `|` دارد اگر نقاط $(i, j)$ و $(i + 1, j)$ با یک خط متصل شده‌اند و علامت . در غیر این صورت است. + سلول در $(2i - 1, 2j)$ علامت `-` دارد اگر نقاط $(i, j)$ و $(i, j + 1)$ با یک خط متصل شده‌اند و علامت . در غیر این صورت است. تضمین می‌شود که هیچ بازیکنی امتیاز نگرفته است: هیچ مربع‌های واحدی هنوز تشکیل نشده‌اند. # خروجی تعداد حرکاتی را که می‌توان انجام داد، در بدترین حالت، قبل از این که امین یا مهدی مطمئن شوند که امتیازی را گرفته‌اند، خروجی دهید. # مثال‌ها ## ورودی نمونه ۱ ``` 3 *-*.* |.|.| *.*-* |...| *.*.* ```` ## خروجی نمونه ۱ ``` 2 ```` ## ورودی نمونه ۲ ``` 2 *.* ... *.* ```` ## خروجی نمونه ۲ ``` 3 ```` ## ورودی نمونه ۳ ``` 4 *-*-*.* |...|.. *-*-*-* |.....| *.*.*-* |.....| *-*-*-* ```` ## خروجی نمونه ۳ ``` 4 ````

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