Печера

Гном Торін знайшов план покинутої печери, у якій жив гірський король Норус. На плані позначено місце, де знаходиться величезний скарб. Гірський король захистив своє багатство від шукачів скарбів, для чого розмістив у печері $L$ кам'яних блоків, які рухаються і можуть розчавити шукача, і які зупиняються, коли скарб знайдено.

План подано у вигляді прямокутної цілої матриці M \times N, елементами якої можуть бути: $-2$ (скарб), $-1$ (стіна), $0$ (порожнє місце), додатне число $K$ (елемент $K$-го блоку). $K$-й блок складається з усіх елементів, позначених числом $K$. Блок не обов'язково зв'язний, але всі його елементи рухаються синхронно. Нулі у крайніх рядках чи стовпцях матриці позначають входи до печери. Окремо вказується початковий напрям руху кожного блоку ($1$ — вгору, $2$ — праворуч, $3$ — вниз, $4$ — ліворуч).

Гном займає клітинку-вхід. Після цього він рухається за такими правилами: протягом кожної секунди першим переміщується гном на порожню клітинку з $4$-х сусідніх (вгору, вниз, вліво чи вправо) або залишається на місці. Потім, протягом тієї ж секунди, переміщується кожен блок на одну клітинку (вгору, вниз, вліво чи вправо): спочатку перший, за ним другий і так далі. Якщо перед яким-небудь елементом у напрямку його руху знаходиться стіна, край печери, скарб чи інший блок, то на цьому ході блок не рухається, а напрямок його руху змінюється на протилежний. Якщо блок під час руху потрапив у клітинку з гномом, то гном гине.

Напишіть програму CAVE для пошуку безпечного шляху, який приведе до скарбу за найменший час, вважаючи, що такий шлях існує.