در یک روز آفتابی، عده‌ی زیادی از مردم نارنجستان به تماشای یک باغ گل در سرزمینی مستطیلی شکل آمده‌اند، که ناگهان، صدای هشدار آتش‌سوزی همه چیز را به آشوب می‌کشد. همه تلاش می کنند که با رساندن خود به در خروجی، جان خود را نجات دهند. متاسفانه باغ تنها یک در دارد. در حالی که همه تلاش می‌کنند جان خود را نجات دهند، مراقب هستند که پا روی گلی نگذارند (گل‌ها در محفظه‌های شیشه‌ای ضد آتش قرار دارند) و به دیگران صدمه نزنند. شما باید برنامه‌ای بنویسید که برای این مردم متمدن بهترین طرح فرار از آتش‌سوزی را مشخص کند.

فرض کنید که باغ در یک جدول مستطیل‌شکل واقع شده‌ است. در هر خانه، تعدادی گل یا مکانی برای ایستادن یک نفر قرار دارد. هر نفر در هر ثانیه می‌تواند خود را به یکی از چهار خانه‌ی مجاور خود برساند. این حرکت در صورتی امکان‌پذیر است که خانه‌ی مجاور، در ثانیه‌ی بعد توسط فردی دیگر اشغال نشده باشد و گلی هم در آن خانه قرار نداشته باشد. توجه کنید که اگر در یک لحظه دو نفر می‌توانند به یک خانه وارد شوند، طرح فرار شما باید فقط یک نفر را به آن خانه وارد کند و نفر دیگر یا صبر کند یا حرکت دیگری انجام دهد. برنامه‌ی شما باید زمان کمینه برای تخلیه‌ی باغ را محاسبه کند، یعنی مدت زمانی که طول می کشد تا همه به در خروجی برسند. می‌توانید در نظر بگیرید همواره برای هر شخص مسیری از خانه‌ی ابتدایی تا در خروجی، بدون پا گذاشتن روی گل‌ها، وجود دارد.

• ورودی از تعدادی سناریو تشکیل شده است. هر سناریو با یک خط شامل دو عدد $n$ و $m$ $(3\leq n,m\leq 100)$ که به ترتیب مشخص کننده‌ی طول افقی و عمودی باغ می‌باشند (اندازه‌ی هر خانه $1\times 1$ است).
• $n$ خط بعدی هر یک شامل $m$ حرف از مجموعه‌ی {#, F, P, -,*} که نمایش‌دهنده‌ی وضعیت باغ، هنگام به صدا در آمدن هشدار آتش‌سوزی هستند. دیواره‌ی اطراف باغ با حرف $”\#”$ نمایش داده می‌شود به جز در خروجی که با $”*”$ نمایش داده می‌شود. هم‌چنین حروف $F$ و $P$ به ترتیب مشخص کننده‌ی آن هستند که در خانه‌ی مورد نظر در زمان هشدار، گل‌هایی یا یک شخص قرار داشته است. خانه‌های خالی در زمان هشدار آتش‌سوزی با $”-“$ نمایش داده شده‌اند.
• ورودی با یک خط شامل $”0\ 0”$ خاتمه می‌یابد.

به ازای هر سناریو در یک خط زمان کمینه برای تخلیه‌ی باغ را چاپ کنید.

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

• سوال بعد
• سوال قبل