XO پیشرفته


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

دو نفر در حال بازی XO پیشرفته هستند. بازی در یک جدول n×nn \times n انجام می‌شود. هر نفر در نوبت خود یکی از خانه‌های جدول را پر می‌کند. نفر اول با X و نفر دوم با O. خانه های خالی با - نمایش داده می‌شود. برنده زمانی مشخص می‌شود که حداقل aa خانه یکسان متوالی به صورت سطری با ستونی یا قطری قرار گیرد.

جدول یکی از مراحل بازی به دست ما رسیده و می خواهیم مرحله بعد بازی را پیش بینی کنیم!

  • اگر بازی تا کنون به اتمام رسیده، Finished چاپ کنید.
  • اگر نفر اول می تواند با یک حرکت بازی را ببرد، X چاپ کنید.
  • اگر نفر دوم می تواند با یک حرکت بازی را ببرد، O چاپ کنید.
  • اگر هر دو می‌توانند با یک حرکت بازی را ببرند، Both چاپ کنید.
  • اگر هیچکدام از موارد بالا نیست، None چاپ کنید.

ورودی🔗

خط اول ورودی دو عدد nn و aa با فاصله از هم آمده است. 2an1002 \le a \le n \le 100 در nn خط بعدی جدول بازی آمده است. خانه های خالی با - مشخص شده است.

خروجی🔗

خروجی برنامه طبق توضیحات یکی از عبارات Finished، X، O، Both یا None است.

مثال🔗

ورودی نمونه ۱🔗

3 3
X-O
-XO
---
Plain text

خروجی نمونه ۱🔗

Both
Plain text

جفت بازیکن‌ها با علامت زدن خانه‌ی آخر سطر سوم می‌توانند برنده شوند.

ورودی نمونه ۲🔗

4 3
O-OO
X---
-X-O
-XXO
Plain text

خروجی نمونه ۲🔗

Finished
Plain text

۳ تا x به صورت قطری در سطر دوم تا چهارم قرار دارد و یعنی بازی تا الان پایان یافته است.

ورودی نمونه ۳🔗

3 3
XOO
X-O
--X
Plain text

خروجی نمونه ۳🔗

X
Plain text

نفر اول با گذاشتن x در خانه‌ی اول سطر سوم می‌تواند برنده شود ولی نفر دوم نمی‌تواند برنده شود.

ورودی نمونه ۴🔗

4 4
X--X
OO--
X---
---X
Plain text

خروجی نمونه ۴🔗

None
Plain text

هیچ کدام از بازیکنان با یک حرکت نمی‌توانند برنده شوند.