+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- *وقتی که بچه‌های دوره داشتند وارد رستوران می‌شدند دیدند که نه از شازززیا خبری هست نه از آقا تیزی، فهمیدند که سرشان کلاه رفته و افتادند دنبال شازززیا.* نقشه‌ی شازززلند به شکل یک جدول $ n \times m $ است که هر خانه از آن یا خیابان است یا ساختمان. شازززیا و بچه‌های دوره هم در دو خانه متفاوت قرار دارند. (طبیعتا فقط از خیابان‌ها می‌توان عبور کرد.) همه می‌دانند که یک خانه هم در نقشه هست که در آن یک پورتال، به یک دنیای آینه‌ای که شازززیا هم می‌خواهند به آن فرار کنند، وجود دارد. چون نقشه‌ی شازززلند با ماهواره رصد می‌شود، شازززیا نقشه را به صورت آنلاین در دسترس دارند و از آنجایی که بچه‌های دوره هم هکرهای ماهری هستند، می‌توانند به نقشه آنلاین دسترسی داشته باشند. شازززیا سوار یک ماشین شده‌اند که برای حرکت نیاز به یک کد ثابت دارد. (کدی از حرکات بالا، پایین، چپ یا راست) که اول کار باید کد را به آن بدهند. ماشین هم با توجه به آن کد حرکت می‌کند و دیگر کد قابل تغییر نیست. از آنجایی که در فرایند رای گیری برای انتخاب کد غوغایی به پا شد، بچه‌های دوره هم کدی که شازززیا به ماشین می‌دهند را می‌دانند. در هر ثانیه ماشین شازززیا یک حرکت در جدول می‌کند و بعد از آن در همان ثانیه بچه‌های دوره می‌توانند یا یک حرکت دلخواه بکنند یا سرجایشان بمانند. هر حرکت هم یعنی حرکت به یکی از خانه های مجاور ضلعی. (بالا، پایین، راست، چپ) در پایان هر ثانیه - اگه شازززیا و بچه‌های دوره در یک راستا (سطر یا ستون) قرار بگیرند که بینشان ساختمانی نباشد، بچه‌های دوره شازززیا را اسیر می‌کنند. - اگه شازززیا اسیر نشوند و به پورتال برسند، می‌توانند فرار کنند و دست بچه‌های دوره به آن‌ها نمی‌رسد. از آنجایی که هم بچه‌های دوره هم شازززیا در تعقیب و گریزند از شما انتظار می‌رود که برنامه‌ای بنویسید که مشخص کند آیا شازززیا می‌توانند اول کار کدی را به ماشینشان بدهند که به پورتال برسند و از دست بچه های دوره فرار کنند یا نه؟ # ورودی خط اول ورودی به ترتیب شامل $n$ و $m$ که نشان دهنده ابعاد نقشه شازززلند است، داده می‌شود. هر کدام از $n$ خط بعدی شامل رشته‌ای به طول $m$ است. هر حرف از آن رشته نشان دهنده یک خانه از جدول است که اگر `.` باشد یعنی خیابان است، اگر `B` باشد ساختمان است، اگر `D` باشد نشان دهنده جای بچه‌های دوره است، اگه `S` باشد نشان دهنده جای شازززیاست و در نهایت `P` هم پورتال است. $$ 1 \le n, m \le 700 $$ # خروجی در تنها خط خروجی `YES` چاپ کنید اگر شازززیا می‌توانند بدون اسیر شدن توسط بچه های دوره با تعیین یک کد اولیه برای ماشینشان به پورتال فرار کنند و در غیر آن `NO` چاپ کنید. # زیرمسئله‌ها | زیرمسئله | نمره | محدودیت |:------------------:|:----------:|:------------------:| | ۱ | ۵۰ | $$ 1 \le n,m \le 200 $$ | | ۲ | ۵۰ | بدون محدودیت اضافی | # مثال ## ورودی نمونه ۱ ``` 5 7 S.....D ..B.... ..BBBBB ....... ...P... ``` ## خروجی نمونه ۱ ``` YES ``` توضیح نمونه: شازززیا می‌توانند با کد زیر موفق شوند: پایین - پایین - پایین - راست - راست - راست - پایین ## ورودی نمونه ۲ ``` 5 7 S....D. ..B.... ..BBBBB ....... ...P... ``` ## خروجی نمونه ۲ ``` NO ``` ## ورودی نمونه ۳ ``` 2 3 .SP DBB ``` ## خروجی نمونه ۳ ``` NO ``` توضیح نمونه: اگر همزمان شازززیا به پورتال برسند و بچه‌های دوره هم آن‌ها را ببینند (یعنی هر دو گروه در یک راستا که ساختمانی بینشان وجود ندارد باشند) باز هم شازززیا اسیر می‌شوند. در نمونه دوم و سوم هیچ کدی وجود ندارد که شازززیا را نجات دهد.