احتمالاً بازی Flappy Bird را دیدهاید. در این بازی، یک پرنده از سمت چپ به راست حرکت میکند. مانعها در این بازی یا بخشی از بالا یا پایین صفحه را مسدود کردهاند و هدف این است که پرنده بدون برخورد به موانع به انتهای بازی برسد.
در نسخهی سادهشدهی این بازی، فرض کنید کل محیط بازی بهصورت یک جدول است. هر خانه از جدول میتواند یکی از سه وضعیت زیر را داشته باشد:
در ابتدا، میدانیم که پرنده در خانهی بالا-چپ قرار دارد و قصد دارد به خانهی پایین-راست برود (تضمین میشود که این دو خانه هیچگاه مانع ندارند). پرنده میتواند در هر حرکت به خانههای مجاور ضلعی (در صورت نبود مانع) حرکت کند. سوال این است که آیا پرنده میتواند مسیری برای رسیدن به مقصد پیدا کند یا نه؟
برای درک بهتر سوال، به نمونهها مراجعه کنید.
در سطر اول ورودی، عدد صحیح و مثبت داده میشود که تعداد ستونهای جدول را نشان میدهد.
در دو سطر بعدی، هر سطر شامل کاراکتر است که کاراکتر سطر ام و ستون ام وضعیت خانهی متناظر در جدول را مشخص میکند. کاراکتر X
نشاندهندهی مانع و کاراکتر O
نشاندهندهی باز بودن خانه است.
خانهی سطر اول از ستون اول و خانهی سطر دوم از ستون ام مبدا و مقصد پرنده هستند و همیشه با O
مشخص میشوند.
در تنها سطر خروجی، در صورت وجود مسیر، رشتهی Hooraaay!:))
و در غیر این صورت رشتهی Awww:((
را چاپ کنید.