+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- خسرو که یکی از کارمندان منظم شرکت رهنما است، هر روز صبح نیم ساعت قبل از شروع ساعت کاری در شرکت حاضر شده و تا شروع ساعت کاری $minesweeper$ بازی می‌کند، اما اغلب اوقات بازی وی نیمه تمام می‌ماند. حال ما به شما جدول نیمه تمام بازی خسرو را می‌دهیم و از شما می‌خواهیم که جدول کامل را حدس بزنید و خانه‌های خالی جدول را تکمیل کنید. ** هر خانه از یک جدول $minesweeper$ : ** * یا شامل یک بمب است که در این صورت با کاراکتر ′∗′ نمایش داده می‌شود. * یا شامل بمب نیست و تعداد ناصفری از خانه‌های مجاور رأسی آن (۸ خانه همسایه‌اش) شامل بمب‌اند که در این صورت با تعداد بمب های خانه‌های مجاور رأسی‌اش نشان داده می‌شود. * یا نه خود شامل بمب است نه خانه های مجاور رأسی‌اش که در این صورت با کاراکتر ′.′ (نقطه) نمایش داده می‌شود. از آن جایی که ما می‌خواهیم شما بیشترین نمره را از این سوال بگیرید ، حتی اگر در جدول نهایی تعداد بمب‌های مجاور‌ رأسی یک خانه از عدد داخل آن خانه (در صورت وجود) **کمتر** بود باز هم ما از شما این جدول را به عنوان جدولی نهایی قبول می‌کنیم؛ به عبارتی دیگر به ازای هر خانه شامل عدد در جدول نهایی کافیست تعداد بمب‌های مجاور رأسی آن خانه *کمتر یا مساوی* عدد نشان داده شده در آن خانه باشد. **دقت کنید که شما فقط باید خانه‌های مجهول جدول را تکمیل کنید (تبدیل به ′.′ یا ′∗′ و یا عددی بین ۱ تا ۸ ) و باقی خانه‌ها را بدون تغییر رها کنید. دقت کنید که باید تمام خانه‌های مجهول را پر کنید. ** **برای آشنایی بیشتر با بازی minesweeper می‌توانید به [اینجا](https://en.wikipedia.org/wiki/Minesweeper_%28video_game%29) مراجعه کنید. ** # نمره‌دهی از نظر ما هر چه تعداد بمب‌های یک جدول $minesweeper$ بیشتر باشد زیبایی آن جدول هم بیشتر است در نتیجه هرچه جدول تکمیل شده توسط شما بمب‌های بیشتری داشته باشد نمره بیشتری از این سوال خواهید گرفت. **نیازی نیست بیشترین تعداد بمب را در خانه‌های مجهول قرار دهید تا نمره بگیرید! با کمی بمب قرار دادن شما می‌توایند نمره‌ی خوبی از این سوال را دریافت کنید.** # ورودی در خط اول ورودی دو عدد $n$ و $m$ که به ترتیب طول و عرض جدول است به شما داده می‌شود. $$1 \le n, m \le 100$$ در $n$ خط بعدی در هر خط $m$ کاراکتر می‌آید که جدول نیمه کاره $minesweeper$ را توصیف می‌کند. اگر خانه‌ای حاوی بمب باشد کاراکتر ′*′ اگر خانه‌ای حاوی بمب نباشد و همچنین مجاور هیچ بمبی نباشد کاراکتر ′.′ اگر خانه‌ای مجاور تعدادی بمب باشد تعداد بمب های مجاور آن خانه (که عددی بین $1$ تا $8$ است) و در نهایت اگر خانه‌ای هنوز باز نشده باشد و مجهول باشد کاراکتر ′?′ گذاشته می‌شود. **تضمین می‌شود که حداقل یک راه برای تکمیل جدول به صورتی که با شرایط گفته شده مطابقت کند وجود دارد.** # خروجی در خط اول خروجی حداکثر تعداد بمب‌ها را چاپ کنید. در $n$ خط بعدی در هر خط با $m$ کاراکتر جدول نهایی (حل شده) را مشخص کنید. **جدول خروجی باید از کاراکتر‌های '.' و '*' و اعداد ۱ تا ۸ تشکیل شده باشد و به ازای هر خانه شامل عدد تعداد خانه‌های مجاور رأسی شامل بمب آن خانه از عدد آن خانه بیشتر نباشد. ** # مثال **این مثال‌ها جهت آشنایی شما با جداول درست هستند؛ نیازی نیست که خروجی شما دقیقاً مانند این‌ها باشد و یا تعداد مین‌هایی که در خروجی قرار می‌دهید این مقدار باشد.** ## ورودی نمونه ۱ ``` 2 3 ??? ??? ``` ## خروجی نمونه ۱ ``` 6 *** *** ``` البته این خروجی هم یک جدول درست است: ``` 0 888 888 ``` اما چون هیچ مینی به جدول اضافه نکرده، نمره‌ی خاصی دریافت نخواهد کرد. ## ورودی نمونه ۲ ``` 3 3 ?3* *6* *** ``` ## خروجی نمونه ۲ ``` 6 13* *6* *** ``` ## ورودی نمونه ۳ ``` 5 5 221.. ?*?.. ????. ***?? 2321? ``` ## خروجی نمونه ۳ ``` 7 221.. **2.. **41. ***1. 2321. ```

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