بنت نقشه گنجی پیدا کرده است. این نقشه یک سالن بزرگ را نشان می دهد که چند ورودی دارد و در هر ورودی تعدادی دینامیت قرار دارد که بنت می‌تواند آن‌ها را بردارد. در بعضی از مکان‌ها مانعی وجود دارد که بنت می‌تواند در زمانی ناچیز آن را با دینامیت منفجر کند و یا چند روز با وسایلی که همراهش دارد آن را بتراشد تا آن از بین برود. او تنها می‌تواند در ۴ جهت اصلی حرکت کند و باید از یکی از ورودی‌ها وارد شود. پس از ورود به سالن او دیگر نمی‌تواند به یک ورودی برود.

او از شما خواسته است که برنامه‌ای بنویسید که نقشه سالن را گرفته و به بنت بگوید که حداقل چند روز نیاز دارد تا به گنج برسد.

در ورودی چند سناریو آمده است. در هر سناریو نقشه سالن از دید بالا به شما داده شده است.

راهنمای نقشه‌:

کاراکتر *‌ : مانعی که بنت به هیچ وجه حتی با تمام دینامیت‌هایش نمی‌تواند آن را از بین ببرد.

کاراکتر $ : نشان‌دهنده مکان گنج است.

اعداد 1 تا 9 : مانعی که بنت می‌تواند با دینامیت در زمانی ناچیز و با وسایلش در تعداد روز برابر با عدد نابود کند.

کارکتر # : تنها در مرز نقشه می‌آید و نشان‌دهنده یک ورودی با تعداد دینامیت صفر است.

حروف بزرگ انگلیسی : تنها در مرز نقشه می‌آید و نشان‌دهنده یک ورودی با تعداد دینامیت برابر با رتبه آن کاراکتر در بین حروف انگلیسی است. ( $A = 1, B = 2,...$)

کاراکتر .‌(نقطه) : نشان‌دهنده یک راهرو است. سرعت راه رفتن بنت خیلی زیاد است پس زمانی که برای حرکت او صرف می‌شود را در نظر نمی گیریم.

یک خانه مرزی یا یک ورودی است و یا یک *.

طول و عرض نقشه حداقل ۳ و حداکثر ۱۰۰ کاراکتر است.

خط پایان هر سناریو یک خط خالی و خط آخر ورودی تنها شامل »–» است.

به ازای هر سناریو،‌ اگر بنت می‌تواند به گنج برسد، حداقل تعداد روزی را چاپ کنید که او نیاز دارد تا به گنج برسد، مگر نه چاپ کنید IMPOSSIBLE.

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

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